[Tutor] Working with prime numbers

Steven D'Aprano steve at pearwood.info
Thu Jan 8 06:25:42 CET 2015

Generating prime numbers is a programming problem that many beginners 
are interested in. For those who are, you may be interested in my 
PyPrimes project:

At long last, I am pleased to announce the latest version of PyPrimes, a 
pure Python package for working with prime numbers.

PyPrimes is compatible with Python 2 and 3, and includes multiple 
algorithms for the generating and testing of prime numbers, including 
the Sieve of Eratosthenes, Croft Spiral, Miller-Rabin and Fermat 
probabilistic tests.



Generate prime numbers on demand:

py> it = pyprimes.primes()
py> next(it)
py> next(it)

Test whether numbers are prime:

py> pyprimes.is_prime(23)

Generate primes between an upper and lower limit:

py> import pyprimes
py> list(pyprimes.primes(11000000, 11000500))
[11000027, 11000053, 11000057, 11000081, 11000083, 11000089, 11000111,
 11000113, 11000149, 11000159, 11000179, 11000189, 11000273, 11000281,
 11000287, 11000291, 11000293, 11000299, 11000347, 11000351, 11000369,
 11000383, 11000387, 11000393, 11000399, 11000401, 11000419, 11000441,
 11000461, 11000467]

Find the previous and next primes from a given value:

py> pyprimes.prev_prime(10**9)
py> pyprimes.next_prime(999999937)

Find the prime factorisation of small numbers:

py> import pyprimes.factors
py> pyprimes.factors.factorise(999999997)
[71, 2251, 6257]

Pyprimes also includes examples of naive and poor-quality, but popular, 
algorithms which should be avoided:

py> from pyprimes.awful import turner
py> it = turner()
py> [next(it) for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71]

Study the source code of the "awful" module to see what not to do!


As PyPrimes is written entirely in Python, it is not suitable for 
demanding high-performance applications, but performance can be quite 
reasonable for less-demanding applications. On a laptop with a AMD 
Turion(tm) II P520 Dual-Core Processor, it takes 0.005 second to 
generate the first prime larger than 2**63, and about 10 seconds to 
generate the first one million primes. Testing whether 2**63+7 is prime 
takes under 0.1 millisecond.

Installing PyPrimes

You can download PyPrimes from here:


For Windows users, run the installer. For Linux, Mac and Unix users, 
unpack the source tarball and follow the instructions.

You can also install using pip:

    pip install pyprimes==0.2.1a

(Note: pip may have problems downloading the right version if you don't 
specify a version number.)

Or you can access the latest development version:

    hg clone https://code.google.com/p/pyprimes/


More information about the Tutor mailing list