#### Archived

This topic is now archived and is closed to further replies.

# 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>";

}

2. You can stop at sqrt($num). 1. You can also skip mod 3 numbers too 2. I thought you stopped at num/2 ? #### 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 on other sites

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).

##### 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 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

×

• #### Activity

• Chat
×
• Create New...