python / python/cpython

Add math.integer.isprime() and math.integer.primes()

Open
#153,222 8 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

extension-modules type-feature
Dominant language
Python
Stars
77.2k
Forks
35.9k
PR merge metrics
PR metrics pending

Description

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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the math.integer module entry point and the linked PR gh-153224, since the issue provides the proposed APIs, bounds, examples, and algorithm requirements. Done means implementing and testing isprime() and primes() with exact behavior for the documented inputs, limits, and iterator semantics.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, python
Domain
backend
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.