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.

This week I have been mostly reading blog.Stealthcopter.com and it’s been really helpful. So thanks for that. Just a point i’ve already let you know about; instead of check += 1 you can do check += 2 as once you’ve eliminated the posibility of an even factor, the rest disapear!

until next time!

– Meat

Thanks mike, have update the post with your suggestion and some benchmarks!

Use sieve, fast and smooth !!

Not in this case, as using the sieve to check a single number is very inefficient and wastes a lot of memory. If I wanted to get a list of all the primes up to a certain number then using the sieve method would be appropriate.

Okay, I’ve looked through your blog a few times and what you’re writing here is C using python syntax.

I’m sorry to sound so critical, but, in this example in particular, your code is, frankly, terrible python. And it’s slow.

Try this:

import math

def prime_test(num):

….if num is 2:

……..return True

….else:

……..for n in range(3, int(math.sqrt(num)), 2):

…………if num % n:

…………….continue

…………else:

…………….return False

……..return True

In my ipython shell:

%timeit -n1000 -r10 isprime(982451653) #improved version

1000 loops, best of 10: 6.25 ms per loop

%timeit -n1000 -r10 prime_test(982451653)

1000 loops, best of 10: 2.69 ms per loop

Python has many high level constructs. They are what make the language so powerful.

d’oh! Off-by-1 error. Should be int(math.sqrt(num))+1

Now I’m really making myself look bad: I forgot to test num is even or 1… So, an additional ‘elif num is 1 or num % n is 0: return False’ is necessary. Nonetheless, that only boosts the average time per loop by 0.1 ms to 2.79.

Don’t worry about criticism as I’d much prefer to be embarrassed and have learnt something, than proud and ignorant. I am more used to writing code using C style but I’m trying to learn all the loveliness that python offers.

The main speed advantage in your program over mine is provided by the limit (sqrt(number)) which is something I was looking into but I wanted to find a proof for it before using it.

Your program also doesn’t handle numbers below 1. I didn’t realise range had an optional third parameter for steps, this will be very useful for me, thanks!

One thing I don’t understand is why you’d need to use else so much. I.E.

….if num is 2:

……..return True

….else:

as you will return if num is 2, there is no need to use an else statement and it just takes up room. And I’d change this

…………if num % n:

…………….continue

…………else:

…………….return False

to

…………if not num % n:

…………….return False

and I’d change my original code to:

I dug around a year or so ago and came up with what I think is a pretty fast algorithm applying the Miller-Rabin primality test and implemented in python. Testing the 9th Mersenne prime, 2305843009213693951 takes ~0:00:00.002065. Try the 6th Fermat number (18446744073709551617 = 18446744073709551617 = 274177 × 67280421310721). Fermat conjectured they were all prime but Euler factored #5 in 1792. Time to determine not prime: 0:00:10.347881.

http://www.tiawichiresearch.com/?p=44

By and large, the extra ‘else’s don’t make much of a difference in the bytecode, but they do help the readability. And, frankly, if you’re writing code in python, readability is key. Optimizations in python are usually of the logical (algorithmic) sort, rather than code optimization. Really, the inclusion or exclusion of ‘else’s within the logic is semantic.

I did totally forget about negative numbers, probably because no one cares about negative prime numbers and I wasn’t worried about completeness (hence my ADD-fueled additional posts in what was the middle of the night for me). If I were writing a library, I’d have tests to prevent this sort of thing.

As for the question of whether you need to search higher than the sqrt of the number, every factor greater than the sqrt of the number will have a match that is less than the sqrt of the number.

Also, your revised program still fails for 2.

If I were to write a ‘proper’ version, it would be:

def prime_test(n):

.. if n < 2 or n % 2 == 0:

…. return False

.. elif n == 2:

…. return True

.. else:

…. for i in range(3, int(math.sqrt(n))+1, 2):

…… if n % i == 0:

…….. return False

…. return True

If you want speed, however, find a library where someone else has worried about such things, such as sympy.

%timeit assert sympy.isprime(2**61-1)==True # 9th Mersenne prime

1000 loops, best of 3: 743 µs per loop

%timeit assert sympy.isprime(2**89-1)==True # 10th.

1000 loops, best of 3: 1.22 ms per loop

%timeit assert sympy.isprime(2**(2**6)+1)==False # 6th Fermat number

1000 loops, best of 3: 324 µs per loop

And for reference to my previous post, the redefined prime_test vs. sympy:

%timeit -n1000 -r10 assert prime_test(982451653)==True # Mine

1000 loops, best of 10: 2.51 ms per loop

%timeit -n1000 -r10 assert sympy.isprime(982451653)==True # sympy

1000 loops, best of 10: 133 µs per loop

if n <= 2 or n % 2 == 0:

return n == 2

else:

…

…

write program to check if any given number is prime or not??

how can i see how fast my code runs?