[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
===================
You can download PyPrimes from here:
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:
hg clone https://code.google.com/p/pyprimes/
--
Steve
More information about the Tutor
mailing list