Skip to content

Python: Checking if a number is prime

by mat on September 3rd, 2009

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.

13 Comments
  1. 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

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

  3. Use sieve, fast and smooth !!

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

  5. Ben permalink

    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.

  6. Ben permalink

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

  7. Ben permalink

    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.

  8. 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:

    def isprime(number):
    	if number< =1 or number%2==0:
    		return 0
    	for check in range(3,int(math.sqrt(number))+1,2):
    		if number%check==0:
    			return 0
    	return 1
    
  9. 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

  10. Ben permalink

    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

  11. st0le permalink

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

  12. karrar permalink

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

  13. how can i see how fast my code runs?

Leave a Reply

Note: I am currently writing my thesis so probably wont have time to reply to your comment
Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS