This function return a list of numbers which is less than argument. It is much faster than other implementations which I test. At my machine, prime_numbers_less_than(100000) takes about 0.78sec. This code is tested at Python 2.3.4 only.
Python, 15 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def prime_numbers_less_than(N):
if N <= 3:
return range(2,N)
primes = [2] + range(3,N,2)
index = 1
max = N ** 0.5
while 1:
i = primes[index]
if i>max:
break
index += 1
primes = [x for x in primes if (x % i) or (x == i)]
return primes
|
Does seem to be fast. When I tried your code, it seemed to be a bit more than twice the speed of the prime generator I wrote in http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117119 and (a somewhat more elaborate version) http://www.ics.uci.edu/~eppstein/PADS/Eratosthenes.py
On the other hand, yours needs to know N in advance, while mine doesn't, and the PADS version of mine uses much less memory if you don't need to keep a list of all the primes you're generating (O(sqrt N) instead of O(N)). So both might be useful in different situations.
Suggest rewriting this as a generator. I'd suggest rewriting this as a generator, which would reduce the memory requirement as well as the issue of having to know N in advance.
Can still be speeded up. It's a nice algorithm when N is not too large, but can still be speeded up (by 40-50% on my machine):
Split the list into [primes], [candidates] so the x == i test can be removed from the inner loop and to reduce the size of all the lists that are produced.
filter() can move the x % i test from Python to C code.
Special-case small primes to save some speed and memory.
Convert max to int, since integer comparison is faster than floating-point comparison (i > max).
While I was at it, I fixed prime_numbers_less_than(5.2), and renamed max to top since there is a built-in function 'max'.
more speed...? I wonder if this could be sped up even more by noticing that all primes are congruent with either 1 or 5 mod 6 and none are congruent with 0 mod 5. This reduces the number of candidate primes by about 50%, i.e. these conditions apply to only about half of the odd integers. BTW, I tried posting some code in here and got weird results. Can someone tell me why that is?
Already done. "None (above 5) are congruent with 0 mod 5" is caught by the x % 5 test. "Congruent with either 1 or 5 mod 6" = "not congruent with 0 mod 2 or 3", which is caught by xrange(,,-2) combined with the x % 3 test.
ah, I see that now...cleverly done...:-)