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 = [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

6 comments

David Eppstein 17 years, 4 months ago  # | flag

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  # | flag

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  # | flag

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  # | flag

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  # | flag

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  # | flag

ah, I see that now...cleverly done...:-)

Created by Kazuo Moriwaka on Sat, 17 Jul 2004 (PSF)
Python recipes (4591)
Kazuo Moriwaka's recipes (2)

Required Modules

  • (none specified)

Other Information and Tasks