Jump to content
Sanjib Sinha

To test a prime number

Recommended Posts

I have written a function to check whether any number is prime or not.

Is it okay? or I can better it by any means?



function isPrime($num){
$number = array();
for ($i=2; $i <= $num; $i++){
if(($num%2)==0){
continue;
}
if (($num%$i)==0){
break;
}
$number[]=$i;

}
/*
* how I back calculate to make it successful
foreach ($number as $key => $value) {
echo "$key = $value <br>";

}
echo count($number);
*/
if (count($number)== ($num-2))
{
echo 'it is prime';
}
else {
echo 'not prime';

}
}

isPrime(101112345909);

Edited by Sanjib Sinha

Share this post


Link to post
Share on other sites

1. You can start at $i=3 and skip even numbers.

2. You can stop at sqrt($num).

3. Make your function return true/false instead of outputting a string.

4. There's absolutely no need to keep track of all those $numbers: if it's divisible by $i then false, and make it return true after the loop finishes.

5. Research other methods of determining primes.

  • Like 1

Share this post


Link to post
Share on other sites

I had searched web and found some of them very interesting and few of them seem complex like this one in wiki:

function isPrime($n) {
    if ($n <= 3) {
        return $n > 1;
    } else if ($n % 2 === 0 || $n % 3 === 0) {
        return false;
    } else {
        for ($i = 5; $i * $i <= $n; $i += 6) {
            if ($n % $i === 0 || $n % ($i + 2) === 0) {
                return false;
            }
        }
        return true;
    }
}

Specially this part:

for ($i = 5; $i * $i <= $n; $i += 6) {
            if ($n % $i === 0 || $n % ($i + 2) === 0) {
                return false;
            }
        }

It started from 5. It is okay. But the logic flow seems pretty complex. Can anyone translate in simple English actually what is happening?

Share this post


Link to post
Share on other sites

Thanks 

IThinkMyBrainHurts

I guessed something like this. But why should I go for such complexity?

Please consider this code to test the primality:

function is_prime($num)
{
    for($i=2; $i<= (int)sqrt($num); $i++){
        if($num % $i == 0) {
            return false;
        }
    }
    return true;
}

if(is_prime(119)){
    echo 'Prime';
}
 else {
    echo 'Not Prime';
}

//output not prime 

Share this post


Link to post
Share on other sites

Starting from 5, the 3 is tested by the mod 3 later, 4 is not a prime. This part is neither here nor there really.The loop step size means that it makes 6 times fewer checks than the other version, and if you're testing say 104729 (the 10,000th prime), that's what 17,454 times more efficient, and that prime is tiny when it comes to public key encryption.*** Looks like it only makes it 3 times faster?

 

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 \scriptstyle{}\leq\sqrt n. This is 3 times as fast as testing all m.
http://en.wikipedia.org/wiki/Primality_test* My knowledge on the subject is over 10 years old now, also it was only a personal interest

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.