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.

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

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:

Increasing the upper bound by a factor of 10, to ten million, takes almost

thirtytimes longer, 450 seconds or so:Here are some tips to speed it up:

Your is_prime function does

wayto 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".

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.

Maybe a bit faster(or a lot)

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