To test a prime number

[Sanjib Sinha]

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 April 19, 2015 by Sanjib Sinha

[requinix]

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.

[NotionCommotion]

5. Research other methods of determining primes.

Maybe http://en.wikipedia.org/wiki/Primality_test

[IThinkMyBrainHurts]

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

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

 

1. You can also skip mod 3 numbers too

2. I thought you stopped at num/2 ?

[Sanjib Sinha]

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?

[IThinkMyBrainHurts]

It loops from 5 up to the square of i less than your number with a step of 6.

It then uses mod (%) to find out if divisible (e.g. = 0).

[Sanjib Sinha]

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 

[IThinkMyBrainHurts]

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