Prime number module
Alex Martelli
aleax at aleax.it
Mon Sep 29 18:01:38 CEST 2003
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
More information about the Python-list
mailing list