fluttersmith/py-snippetsGitHub ↗
pysnippets.numbers.is_prime

Check if a number is prime

Test primality by trial division up to the integer square root.

Numbers#validationO(√n) time✓ 3 examples pass on 3.11–3.14

Fine up to about 10¹². For bigger numbers, use a probabilistic test like Miller–Rabin.

is_prime.py✓ ruff · mypy --strict
from math import isqrt


def is_prime(n: int) -> bool:
    """Return ``True`` if ``n`` is a prime number."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    return all(n % d for d in range(3, isqrt(n) + 1, 2))
  1. isqrt is exact; int(sqrt(n)) can be off by one for huge n
examples✓ 3 doctests · 3.11–3.14
>>> is_prime(11)True>>> [n for n in range(20) if is_prime(n)][2, 3, 5, 7, 11, 13, 17, 19]>>> is_prime(-7)False
Edit the function or the examples and run the doctests here, on Python 3.14. Python loads only when you click (about 7 MB, cached after the first time).

How it works

  • Numbers below 2 aren’t prime; 2 and 3 are.
  • Even numbers are ruled out once, then only odd divisors are tried.
  • A divisor above √n would pair with one below it, so the search stops at isqrt(n).

Complexity: O(√n) time, O(1) space

Importfrom pysnippets.numbers.is_prime import is_primeNo dependencies: copy is_prime.py into your project, or clone the repo.

Adapted from is-prime in 30-seconds-of-python by the 30 seconds of code contributors, CC BY 4.0. Changed: Uses math.isqrt, which stays exact for huge n where int(sqrt(n)) rounds; typed. Suggest an edit.