Primality Testing

The decision table

Range	Method	Cost
Single $n\le 10^{12}$	trial division to $\sqrt{n}$	$O(\sqrt{n})$
Single $n\le 2^{64}$	deterministic Miller-Rabin	$O({\log }^{3}n)$
All primes up to $10^7$	sieve of Eratosthenes	$O(n\log \log n)$
All primes up to $10^9$	segmented sieve	$O(n\log \log n)$, $O(\sqrt{n})$ memory
Primes in $[L,R]$ with $R-L$ small	segmented sieve	$O((R-L)\log \log R+\sqrt{R})$
Mersenne numbers $2^p-1$	Lucas-Lehmer	$\tilde{O}(p^2)$
Cryptographic sizes, need a proof	ECPP	heuristic $\tilde{O}({\log }^{4}n)$
Theoretical interest	AKS	$\tilde{O}({\log }^{6}n)$

Trial division

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

Only test 2, 3, then $6k\pm 1$ to cut the work by a factor of 3. Fine up to $10^{12}$; hopeless beyond.

Deterministic Miller-Rabin for 64-bit

The practical answer. Testing the bases $\{2,3,5,7,11,13,17,19,23,29,31,37\}$ is provably correct for every $n<2^{64}$. See Miller-Rabin.

for (u64 a : {2,3,5,7,11,13,17,19,23,29,31,37})
    if (witness(a, d, n, s)) return false;
return true;

Smaller sufficient sets exist for smaller bounds: $\{2,3,5,7\}$ for $n<3.2\cdot 10^9$, $\{2,7,61\}$ for $n<4.8\cdot 10^9$.

Sieve of Eratosthenes

vector<bool> sieve(int n) {
    vector<bool> isComposite(n + 1, false);
    for (int i = 2; (long long)i * i <= n; i++)
        if (!isComposite[i])
            for (int j = i * i; j <= n; j += i) isComposite[j] = true;
    return isComposite;
}

Starting the inner loop at $i^2$ (not $2i$) is the standard optimisation — smaller multiples were already marked.

Linear sieve ($O(n)$) additionally gives the smallest prime factor of every number, which makes factorisation $O(\log n)$ per query:

vector<int> spf(n + 1, 0), primes;
for (int i = 2; i <= n; i++) {
    if (!spf[i]) { spf[i] = i; primes.push_back(i); }
    for (int p : primes) {
        if (p > spf[i] || (long long)i * p > n) break;
        spf[i * p] = p;
    }
}

Each composite is marked exactly once — by its smallest prime factor.

Segmented sieve

To find primes in $[L,R]$ with $R$ up to $10^{12}$ but $R-L\le 10^6$:

1. Sieve primes up to $\sqrt{R}$.
2. Allocate a boolean array of size $R-L+1$.
3. For each small prime $p$, mark multiples starting at $\max (p^2,\lceil L/p\rceil \cdot p)$.

$O(\sqrt{R}+(R-L)\log \log R)$ time, $O(\sqrt{R}+(R-L))$ memory.

Facts about prime density

Quantity	Value
$\pi (n)$, primes below $n$	$\approx n/\ln n$
$\pi (10^6)$	78 498
$\pi (10^9)$	50 847 534
Gap between consecutive primes near $n$	$O(\ln n)$ on average; max gap below $10^{18}$ is 1476
Probability a random $n$ is prime	$\approx 1/\ln n$
Number of prime factors of $n$ (distinct)	$\le {\log }_{2}n$; on average $\ln \ln n$
Largest number of divisors below $10^{18}$	103 680

The ”$O(\ln n)$ average gap” is worth remembering: to find a prime near $10^{18}$, test about 40 candidates.

Common pitfalls

Three recurring bugs

1. $n=1$ is not prime, and $n<2$ must be handled before anything else.
2. i * i <= n overflows when $n$ is near $2^{63}$ — use i <= n / i or __int128.
3. The Fermat test alone is wrong. Carmichael numbers (561, 1105, 1729, …) pass it for every coprime base. Miller-Rabin’s square-root check is what fixes this.

Related

• Integer Factorization — the harder problem
• Sieve Techniques — sieving for things other than primality
• Pollard’s Rho — pair with Miller-Rabin to factor 64-bit numbers

See also: Miller-Rabin · Sieve of Eratosthenes · Integer Factorization