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

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
 ``` 1 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 =  + 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 ``` David Eppstein 17 years, 4 months ago

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. Hamish Lawson 17 years, 4 months ago

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. Hallvard Furuseth 17 years, 4 months ago

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

``````def primes_less_than(N):
N = int(N) + bool(N % 1)  # Round up floating-point N
primes = [x for x in (2, 3, 5, 7, 11, 13) if x &lt; N]
if N &gt; 17:
candidates = [x for x in xrange((N - 2) | 1, 15, -2)
if x % 3 and x % 5 and x % 7 and x % 11 and x % 13]
top = int(N ** 0.5)
while (top+1) * (top+1) &lt;= N:
top += 1
while 1:
p = candidates.pop()
primes.append(p)
if p &gt; top:
break
candidates = filter(p.__rmod__, candidates)
candidates.reverse()
primes.extend(candidates)
return primes
`````` Ross La Haye 16 years, 11 months ago

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? Hallvard Furuseth 16 years, 10 months ago

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. Ross La Haye 16 years, 10 months ago

ah, I see that now...cleverly done...:-) Created by Kazuo Moriwaka on Sat, 17 Jul 2004 (PSF)

### Required Modules

• (none specified)