Prime number module

[Alex Martelli]

Dag wrote:

> Is there a python module that includes functions for working with prime
> numbers?  I mainly need A function that returns the Nth prime number and
> that returns how many prime numbers are less than N, but a prime number
> tester would also be nice.  I'm dealing with numbers in the 10^6-10^8
> range so it would have to fairly efficient

gmpy is pretty good for this sort of thing, but the primitives it gives
you are quite different -- is_prime to check if a number is prime, and
next_prime to get the smallest prime number larger than a given number.

You'd have to build your own caching on top of this to avoid repeating
computation if you need, e.g., "how many primes are < N" for several
different values of N; and I'm not even sure that gmpy's primitives are
optimal for this (compared with, for example, some kind of sieving).


Anyway, with all of these caveats, here's an example function:

import gmpy

def primes_upto(N):
    count = 0
    prime = gmpy.mpz(1)
    while prime < N:
        prime = prime.next_prime()
        count += 1
    return count

and having saved it in pri.py, here's what I measure in terms of time:

[alex at lancelot python2.3]$ python timeit.py -s 'import pri' -s 'M=1000*1000'
\
> 'pri.primes_upto(M)'
10 loops, best of 3: 2.76e+06 usec per loop
[alex at lancelot python2.3]$ python timeit.py -s 'import pri' -s
'M=2*1000*1000' 'pri.primes_upto(M)'
10 loops, best of 3: 4.03e+06 usec per loop

i.e., 2.76 seconds for primes up to 1,000,000 -- about 4 seconds
for primes up to 2,000,000.  (This is on my good old trusty Athlon
Linux machine, about 30 months old now and not top-speed even when
new -- I'm sure one of today's typical PC's might take 2 or 3
times less than this, of course).  If I was to use this kind of
computation "in production", I'd pre-compute the counts for some
typical N of interest and only generate and count primes in a
narrow band, I think; but it's hard to suggest anything without a
better idea of your application.


Alex