I’ve been doing a lot of problem solving on Project Euler recently. If your not aware of Project Euler (PE) it is a website with lots of maths / programming based puzzles to solve. Many of the problems involve using or checking prime numbers, in many cases a sieve method would be applicable (see: Sieve of Eratosthenes for a clear explanation / animation).
However sometimes this is not necessary if you only require one prime number, or if memory limitations mean a sieve would be inconceivable. The following is the code I wrote to check if a number is prime or not in python. It tests upwards checking if the number is perfectly divisble, and as it does this it lowers the maximum number need to reach to stop as we know that if a number is not divisible by 2 then it will not be uniquely divisible (a repatition of a divislbe may exist) by anything greater than N/2
def isprime(number):
if number<=1:
return 0
check=2
maxneeded=number
while check<maxneeded+1:
maxneeded=number/check
if number%check==0:
return 0
check+=1
return 1
I hope that this made sense, and is useful to someone. If anyone has any more efficient methods I would be happy to hear from you.
Check out my profile to see which problems I’ve completed. If you’ve completed any I haven’t please get in contact and give me some tips.
Update:
Mike sent a suggestion that I could speed up the program by ignoring all factors of 2, it could also propbably be sped up by looking at 3,4,5 .. etc until certain point.
def isprime(number):
if number<=1 or number%2==0:
return 0
check=3
maxneeded=number
while check<maxneeded+1:
maxneeded=number/check
if number%check==0:
return 0
check+=2
return 1
So lets test the speed difference by doing 1,000 checks of the number 982,451,653 (known to be prime from this usefulsite)
Original Code: 9.99917411804 Seconds elapsed
Improved Code: 5.2977039814 Seconds elapsed
That’s approximately a factor of two speed increase, but this makes me think that a combination of the sieve method with this one may lead to an even further increase.
