Welcome, guest | Sign In | My Account | Store | Cart

"Effcient" Prime Number Generator in Python (Python recipe) by Captain DeadBones
ActiveState Code (http://code.activestate.com/recipes/578402/)

This is a prime number generator in python that I put together for an article I wrote How To Find Prime Numbers In Python

Please Note. This is only efficient per the article discussing this code in the link above. See comments for a better library to generate prime numbers.

Python, 29 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
import math 

def is_prime(num):
	for j in range(2,int(math.sqrt(num)+1)):
		if (num % j) == 0: 
			return False
	return True

def main(argv):

	if (len(sys.argv) != 3):
		sys.exit('Usage: prime_numbers3.py <lowest_bound> <upper_bound>')

	low = int(sys.argv[1])
	high = int(sys.argv[2])
	
	if (low == 2):
		print 2,
	
	if (low % 2 == 0):
		low += 1
		
	for i in range(low,high,2):
		if is_prime(i): 
			print i, 
		
if __name__ == "__main__":
	main(sys.argv[1:])
Tags: prime_generator, prime_number

4 comments

Steven D'Aprano 11 years, 3 months ago  # | flag

I'm afraid that this is not even close to an efficient way to generate prime numbers. If it seems fast, it's because you haven't tried to generate sufficiently large primes.

On my (not very fast) PC, it takes 16 seconds to generate all the primes up to a million:

[steve@ando ~]$ time python2.7 primes.py 0 1000000 > /dev/null
real    0m16.452s
user    0m15.808s
sys     0m0.025s

Increasing the upper bound by a factor of 10, to ten million, takes almost thirty times longer, 450 seconds or so:

[steve@ando ~]$ time python2.7 primes.py 0 10000000 > /dev/null
real    8m5.770s
user    7m39.130s
sys     0m0.571s

Here are some tips to speed it up:

Your is_prime function does way to much work. Once you've checked whether something is divisible by 2, you don't need to bother checking if it is divisible by 4, 6, 8, 10, ...

In fact, you don't need to bother checking whether numbers are divisible by 9, 15, 21, etc. Just check potential primes against known primes.

Even with these tips, your method for generating primes is known as "naive trial division". It's still going to be very slow. There are much faster methods.

You might like to have a look at this:

http://pypi.python.org/pypi/pyprimes

Using this module, I can generate the prime numbers up to ten million in 10 seconds in pure Python. I don't claim that is any sort of record, but if your code is 45 times slower than mine, you shouldn't claim to be "efficient".

Captain DeadBones (author) 11 years, 3 months ago  # | flag

I am afraid you are very correct. The code was not meant to be efficient from a general prospective. The code was wrriten as part of an article and was simply an improvement on another version. That being said I do believe there are many ways that are much faster to generate prime numbers. The library you mentioned is one of them.

smit sanghvi 11 years, 2 months ago  # | flag 
def check(x):
z=True
for i in range(2,x):
    if i<=math.sqrt(x):
        if x%i!=0:
            z=True
        else:
            z=False
            break
    else:
        break
return z
import math

Maybe a bit faster(or a lot)

Russel Walker 10 years, 10 months ago  # | flag

@smit sanghvi I would guess that yours is slower than Captain DeadBones.

Both of you are using trial division, only testing up to the square root of n which is a good optimization for simple trial division. However Captain DeadBones correctly uses math.sqrt() to determine the end argument for range (btw xrange is better), but your code has to call math.sqrt() for every possible divisor and compare it to i.