Sanjib Sinha 0 Posted April 19, 2015 (edited) 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 Quote Share this post Link to post Share on other sites
requinix 816 Posted April 19, 2015 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. 1 Quote Share this post Link to post Share on other sites
NotionCommotion 30 Posted April 19, 2015 5. Research other methods of determining primes. Maybe http://en.wikipedia.org/wiki/Primality_test Quote Share this post Link to post Share on other sites
IThinkMyBrainHurts 3 Posted April 19, 2015 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 ? Quote Share this post Link to post Share on other sites
Sanjib Sinha 0 Posted April 19, 2015 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? Quote Share this post Link to post Share on other sites
IThinkMyBrainHurts 3 Posted April 19, 2015 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). 1 Quote Share this post Link to post Share on other sites
Sanjib Sinha 0 Posted April 20, 2015 Thanks IThinkMyBrainHurtsI 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 Quote Share this post Link to post Share on other sites
IThinkMyBrainHurts 3 Posted April 20, 2015 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 Quote Share this post Link to post Share on other sites