Feature or enhancement

Add prime-number functions to the math.integer module:

• isprime(n, /) -- return True if n is a prime number, False
  otherwise.
• primes(start=2, stop=None) -- return an iterator of the prime
  numbers p with start <= p < stop, in increasing order. If stop
  is None (the default), the iteration does not stop.

The arguments must be less than 2**64; larger values raise
OverflowError.

>>> import math.integer
>>> math.integer.isprime(2**61 - 1)
True
>>> math.integer.isprime(561)
False
>>> list(math.integer.primes(stop=30))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
>>> from itertools import islice
>>> list(islice(math.integer.primes(10**18), 3))
[1000000000000000003, 1000000000000000009, 1000000000000000031]

isprime() uses the deterministic Miller-Rabin test ({2, 7, 61} below
4759123141, Jim Sinclair's seven bases up to 2**64, verified against
the Feitsma-Galway exhaustive list of base-2 strong pseudoprimes), so
the result is always exact. The implementation is small and
self-contained: modular arithmetic on C uint64_t, about a microsecond
for the hardest inputs. primes() tests each candidate with the same
code, so it works for unbounded iteration and for ranges with an
arbitrary large start, with O(1) memory.

Primality testing is one of the most commonly reimplemented number
routines, and hand-written versions are often subtly wrong (trial
division stopping too early, Miller-Rabin with an insufficient base
set) or quadratically slow. PEP 791 explicitly deferred primality
testing out of the initial scope of the module; this proposes it as the
first extension.

Support for larger integers (e.g. a Baillie-PSW implementation in
_pylong.py, following the precedent of other huge-int algorithms
there) can be added later: raising OverflowError now makes that a
backward compatible extension.

Previously discussed in gh-57812 (closed in 2011 with a suggestion to
publish on PyPI; predates the math.integer module).

Linked PRs

• gh-153222: Add math.integer.isprime() and math.integer.primes() #153224