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

https://pypi.python.org/pypi/pyprimes/

Examples
========

Generate prime numbers on demand:

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

Test whether numbers are prime:

py> pyprimes.is_prime(23)
True

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)
999999937
py> pyprimes.next_prime(999999937)
1000000007

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!

Performance
===========

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

https://pypi.python.org/pypi/pyprimes/

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: