Prime Numbers

A prime number is an integer greater than $1$ whose only positive divisors are $1$ and itself. That one-line definition hides the deepest object in number theory: the primes are the multiplicative atoms from which every other integer is built, their individual behaviour is erratic while their collective behaviour is astonishingly regular, and the gap between how easily you can multiply them and how hard it is to un-multiply a number back into them is the foundation the modern digital economy is quietly standing on. This page covers the primes end to end — the mathematics of what is true of them and how that truth was won, the algorithms that generate, test, and factor them in code, and where both are put to work.

A short history

The primes are one of the oldest studied objects in mathematics, and a handful of results mark the road from antiquity to the present:

Euclid, c. 300 BC. Elements Book IX contains the first two theorems that still anchor the subject: that every integer factors into primes, and — Proposition 20 — that there are infinitely many primes. His proof is the model of elegance: if $p_1, \dots, p_k$ were all of them, then $p_1 p_2 \cdots p_k + 1$ is divisible by none of them, so either it is a new prime or has a prime factor outside the list — a contradiction. A generation later Eratosthenes gave the sieve that still bears his name.
Fermat and Euler, 17th–18th c. Fermat's little theorem ($a^{p-1} \equiv 1 \pmod p$ for a prime $p \nmid a$) exposed the arithmetic structure of a prime modulus. Euler proved it, generalised it through his totient function $\varphi(n)$, and recast Euclid's infinitude as an analytic fact — the sum $\sum 1/p$ over primes diverges — the first hint that the primes could be studied with the tools of continuous mathematics.
Gauss, Legendre, Riemann, 19th c. As teenagers, Gauss and Legendre independently conjectured the prime number theorem: the primes thin out like $1/\ln x$. Gauss's Disquisitiones Arithmeticae (1801) also gave the first rigorous proof of unique factorisation. In 1859 Riemann tied the fine distribution of the primes to the complex zeros of the zeta function — the Riemann hypothesis, still unproven, is a statement about how evenly the primes are spread.
1896 and after. Hadamard and de la Vallée Poussin independently proved the prime number theorem. The 20th century then made the primes computational: fast primality tests, the 1977 arrival of RSA, and in 2002 the AKS test — the first deterministic, polynomial-time proof of primality. Much remains open: Goldbach's conjecture, the twin prime conjecture, and the Riemann hypothesis are all still unresolved.

The one structural fact: unique factorisation

Everything else rests on the fundamental theorem of arithmetic: every integer $n > 1$ is a product of primes in exactly one way, up to order —

$$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}.$$

This is why a prime problem is so often really a factorisation problem. The exponent vector $(a_1, \dots, a_k)$ is the true "shape" of a number, and almost every multiplicative quantity is a simple function of it: the number of divisors is $\prod (a_i + 1)$, their sum is a product of geometric series, Euler's totient is $n \prod (1 - 1/p_i)$, and two numbers are coprime exactly when their factorisations share no prime. Whole families of Euler problems are built on reading a number through this lens — counting divisors (problem 12), summing totients, working with semiprimes $n = pq$ (problem 187), prime powers $p^k$ (problem 87), or the largest prime factor of a number (problem 3, public in solutions/public/p0003/). The uniqueness is what lets you compute a global answer prime-by-prime and multiply the pieces together — the same decompose-and-recombine move that the Chinese Remainder Theorem performs on the modulus side.

The lens works in reverse too, and that is where it saves the most. When a problem fixes the value of a multiplicative function and asks which $n$ produce it, the search space is the target's factorisations, not the integers. Problem 248 inverts Euler's totient at $13!$: because $\varphi(p^a) = p^{a-1}(p-1)$, a prime can divide $n$ only if $p - 1$ divides the target, so the $1584$ divisors of $13!$ yield an alphabet of a few hundred candidate primes, and a depth-first search over products of their factors replaces a scan over tens of billions of $n$. One trap is worth knowing: $p = 2$ at exponent $1$ contributes the factor $1$, so every odd solution has an even twin at twice its value, and a search that stops when the residual target reaches $1$ loses half the answers. Problem 241 runs the same kind of search on the abundancy index $\sigma(n)/n$. Each prime power can only raise the index, and the reduced residual $a/b$ must have $b$ dividing the part not yet built. Together those prune a $10^{18}$ range down to about a million partial factorisations. Problem 245 derives structure before it searches at all. If $p^2 \mid n$ then $p$ would divide both $n - \varphi(n)$ and $n - 1$, so every candidate is squarefree. Fixing all but the largest prime then makes the condition linear in that prime, so the program solves for it and tests it rather than looping over it. Problem 516 constrains a property of $\varphi(n)$ rather than its value: it must be 5-smooth. Factor by factor, $p^{a-1}(p-1)$ must be smooth. So a prime above $5$ may appear only once, and only when $p - 1$ is itself a Hamming number. There are $3429$ Hamming numbers below $10^{12}$, and $543$ of them sit just below a prime. A trillion candidates collapse to Hamming numbers times squarefree products of those primes.

Problem 342 asks for which $n$ the totient of $n^2$ is a perfect cube. That is a question about exponents modulo $3$, and what makes it searchable is the direction in which the primes affect each other. A prime $p$ of $n$ contributes $2e - 1$ to its own exponent in $\varphi(n^2)$. Its factor $p - 1$ contributes only to primes strictly smaller than $p$. So I place the primes of $n$ from the largest down. Once the search has passed a prime $q$, no later choice can change $q$'s exponent, so any residue still owed on $q$ must be settled before the search goes below it. That order gives two bounds for free. The largest prime of $n$ receives nothing from the others, so its exponent must be $\equiv 2 \pmod 3$. Then $P^2 \le n$, and a sieve to $\sqrt N$ supplies every prime the search can use. The search tree grows with the number of solutions, not with $N$. The pitfall is a prune that looks stronger than it is. An owed residue on a small prime need not enter $n$ at all, because a later $p - 1$ can cancel it. A lower bound that multiplies in every owed prime at its forced exponent therefore discards real solutions, and only a brute-force cross-check shows it.

Two more problems work on the exponent vector directly. Problem 682 pairs Hamming numbers by their factor count $\Omega$ and by the sum of their prime factors counted with multiplicity. Both are linear in the exponents. So I can tag each prime with a marker $x$ for "one more factor" and $y^p$ for "add $p$ to the sum", which gives the generating function $\prod_{p \in \{2,3,5\}} 1/(1 - x y^p)$. That is the Euler product below, cut down to three primes and given two variables. A finite product of geometric series is a rational function, so the paired count obeys a fixed-order linear recurrence. Its $10^7$-th term then costs a logarithm's worth of small polynomial products. Problem 615 asks for the millionth number with at least a million prime factors. Nothing that size can be listed, but the exponent vector shows where the small ones are. Trading a factor $2$ for an odd prime multiplies the value by at least $3/2$. So among the first $n$ members, all but about $\log_{3/2} n$ of the factors are $2$. Dividing out that shared power of two maps the head of the list onto the same question with $k = 36$, which is an ordinary 64-bit enumeration. The power comes back at the end as a modular exponentiation. Order is what the question asks for, and order survives the scaling even though the values do not.

Divisibility itself is a statement about exponent vectors: $m \mid n$ exactly when every exponent of $m$ is at most the matching exponent of $n$. So divisibility is the componentwise partial order on those vectors. Problem 333 partitions a prime $q$ into numbers $2^i 3^j$, none of which divides another. In exponent space that is an antichain in the grid $\mathbb{N}^2$, and the grid picture gives the recurrence. The odd terms are the pure powers $3^j$, and any two of those are comparable, so an antichain holds at most one. For even $n$ it holds none, and halving every term maps the partitions of $n$ onto those of $n/2$. For odd $n$ it holds exactly one, $3^b$, and the rest halve into a partition of $(n - 3^b)/2$ that uses only powers of $3$ below $b$. Every index falls below $n/2$, so the table fills in doubling blocks. The question only asks whether a count is $1$, so I cap every entry at $2$. "None, one, or many" survives addition, and the table fits in bytes.

The exponent vector also splits a number into its square and squarefree parts. Every $n$ is uniquely $a^2 b$ with $b$ squarefree, and $p^2 \mid n$ exactly when $p \mid a$. Problem 632 counts the $n \le 10^{16}$ with exactly $k$ such square prime factors. "Exactly" is awkward, because it forbids every other prime from appearing squared. "At least these $j$ primes" is easy: for a squarefree $d$, the multiples of $d^2$ number $\lfloor N/d^2 \rfloor$. Each $n$ with exactly $k$ square factors is counted once for every $j$-subset of them, so the "at least" totals are binomial sums of the "exactly" counts. Binomial inversion undoes that triangle with alternating signs. The $k = 0$ count gives a free check: it is the number of squarefree $n \le N$, whose density is $\prod_p (1 - p^{-2}) = 1/\zeta(2) = 6/\pi^2$, the Euler product evaluated at $s = 2$.

Reduce every exponent modulo $2$ and the exponent vector becomes a vector over the two-element field $\mathbb{F}_2$. Multiplying numbers adds their vectors, and a product is a perfect square exactly when the sum is zero. Problem 619 counts the subsets of an interval $[a, b]$ whose product is a square. That is the kernel of a linear map, so the count is $2^{n - r} - 1$ for $n$ numbers whose parity vectors have rank $r$. This is the same linear algebra that the quadratic sieve uses to factor large numbers. The obstacle is width: there is one coordinate per prime up to $1.2$ million. The way through is a size argument. A number $x \le b$ has at most one prime factor above $\sqrt b$, and only to the first power. Such a large prime is a coordinate that only its own few multiples touch. I pick one of them as the pivot, which adds exactly $1$ to the rank, and XOR it into the others to clear that coordinate. What remains is a matrix with only $\pi(\sqrt b) = 186$ columns, so Gaussian elimination over at most 186 basis rows finishes the job.

Coprimality is the same lens with the exponents reduced to "shares a prime or not". Problem 351 counts the lattice points visible from the centre of a hexagonal orchard. A point $(a, b)$ is hidden exactly when $\gcd(a, b) > 1$, and since $\gcd(a, b) = \gcd(a, a + b)$, the visible points on ring $s$ number $\varphi(s)$. The geometry reduces to one totient sum. Problems 251 and 257 use the same move as a parametrisation tool: split off $d = \gcd$, or reduce a ratio to lowest terms $p/q$, and the leftover coprime parts satisfy a divisibility condition clean enough to count whole families with a single floor division.

Coprimality combined with unique factorisation gives a second tool: coprime factors of a square are squares. If $uv = s^2$ and $\gcd(u, v) = 1$, each prime of $s^2$ appears to an even power and lies entirely in $u$ or entirely in $v$, so both are squares. Problem 764 needs this twice. It reads $16x^2 + y^4 = z^2$ as a Pythagorean triple $(4x, y^2, z)$ in which one leg must be a perfect square. Euclid's parametrisation writes that leg as $(m - n)(m + n)$ or $2mn$, a product of coprime factors. So each factor is a square, or twice a square, and the equation becomes two explicit families in coprime parameters $(a, b)$. Since $z$ grows like their fourth power, about $\sqrt N$ pairs cover $z \le N$.

The same coprimality argument parametrises a ratio. Problem 518 wants prime triples $a < b < c$ with $a + 1$, $b + 1$, $c + 1$ in geometric progression. Write the common ratio in lowest terms as $q/p$. Then $p^2$ must divide $a + 1$, because $\gcd(p^2, q^2) = 1$, and the triple is exactly $(kp^2, kpq, kq^2)$ with $\gcd(p, q) = 1$, each $(k, p, q)$ appearing once. A search over pairs of primes becomes a walk over parameters with $kq^2 \le n$. The parametrisation also decides the order of the tests. "$kq^2 - 1$ is prime" depends only on $(k, q)$, is shared by every $p$, and holds for about one $k$ in $\ln n$. So I test it first, and the loop over $p$ runs only on the survivors.

Coprimality also decides when a set of coin values leaves only finitely many totals unpayable. Problem 718 takes the numerical semigroup generated by $17^p$, $19^p$ and $23^p$. The generators are powers of distinct primes, hence coprime, so only finitely many values are missing and the Frobenius number exists. The same coprimality drives the algorithm. The least member of each residue class modulo $x = 17^p$ (the Apéry set) determines every gap in that class. Because $\gcd(23^p, x) = 1$, the walk $i \cdot 23^p \bmod x$ passes through every class exactly once. Along that one cycle, adding a generator is a running minimum, which replaces Dijkstra's algorithm with a single linear pass.

With only two coprime generators $a$ and $b$, the gaps have a coordinate system of their own. Problem 988 places frogs on the gaps of $\langle a, b \rangle$ so that no frog can reach another with jumps of $a$ and $b$. Every gap is uniquely $ab - ia - jb$ with $i, j \ge 1$. Both coordinate differences are smaller than the generators, so no shift along $(b, -a)$ can help, and the difference of two gaps is payable exactly when one coordinate pair dominates the other. The gaps therefore fill a staircase under the line $ia + jb = ab$, and a valid placement is an antichain in it, the same partial order as problem 333 above. A row-by-row DP over the staircase counts the antichains in $O(ab)$ steps, though there are about $10^{15}$ of them.

When the coprimality condition sits inside a product, the Möbius function removes it. Problem 754 multiplies, for every $n \le 10^8$, the integers up to $n$ that are coprime to $n$. Since $\sum_{d \mid m} \mu(d)$ is $1$ when $m = 1$ and $0$ otherwise, the test "$\gcd(k, n) = 1$" becomes a signed sum over the common divisors $d$. Inside a product, that sum lands in the exponent, as $\mu(d)$. The multiples of each $d \mid n$ then contribute a power of $d$ times a factorial. After swapping the order, the whole product runs over $d$ alone, with $\lfloor N/d \rfloor$ taking only $O(\sqrt N)$ distinct values. The prime modulus $10^9 + 7$ does two jobs here. It exceeds $N$, so no factor vanishes, and by Fermat every exponent, including a negative Mertens difference, can be reduced modulo $p - 1$.

A function of which primes divide $n$ is periodic in $n$ once the primes are fixed. Problem 967 counts the $n \le 10^{18}$ for which the sum of the distinct primes $p \le 120$ dividing $n$ is divisible by $3$. Only $p \bmod 3$ matters, so I track all three remainders together as an element of the group ring $\mathbb{Z}[C_3]$, a triple of integers. The function $x^{S(n)}$ is multiplicative, and it is $1 * h$ with $h$ supported on squarefree $d$, so the count is $\sum_d h(d) \lfloor N/d \rfloor$. That sum runs over the squarefree products of 29 primes, about $7 \times 10^7$ terms, so I split the primes into two groups. For the seven smallest primes, the contribution depends only on $n$ modulo their product $Q \approx 3.2 \times 10^6$. One prefix table over a single period then answers any partial sum in $O(1)$. The convolution runs only over the large primes, about $1.4 \times 10^6$ products. This is a wheel in the wheel-factorisation sense, used to count rather than to skip: the small primes are absorbed into a period, and only the large ones are enumerated.

Factorials are where the exponent vector is cheapest to know. Legendre's formula gives the exponent of $p$ in $n!$ as $\sum_k \lfloor n/p^k \rfloor$ without ever forming $n!$. Problem 675 needs a multiplicative function with value $2e + 1$ on $p^e$, evaluated at every factorial up to $10^7!$. A fresh product over all primes for each factorial would cost about $10^{13}$ steps. But $i!$ differs from $(i-1)!$ only at the primes dividing $i$. So each step multiplies in a ratio for at most $\omega(i)$ primes, and the whole table costs $\sum_p n/p = O(n \log \log n)$, the same bound as the sieve that lists those primes.

Unique factorisation also explains the exotic shapes the problems name. A truncatable prime (problem 37) stays prime as you strip digits; a cuban prime (problem 131) is a prime difference of consecutive cubes; a prime-proof number (problem 200) can never be made prime by changing one digit. Each is a constraint layered on top of primality, and each is tractable precisely because primality is the atom underneath.

How the primes are distributed

Individually the primes look random — the gaps between them are unpredictable, and no simple formula generates them — yet in aggregate they obey the prime number theorem with great precision. Writing $\pi(x)$ for the prime-counting function, the number of primes $\le x$,

$$\pi(x) \sim \frac{x}{\ln x}, \qquad \text{equivalently the } n\text{-th prime } p_n \sim n \ln n.$$

This asymptotic is not a curiosity — it is a practical sizing tool. When a problem asks for "the $n$-th prime" you must allocate a sieve before you know where that prime lands, and $n \ln n$ (with a small safety margin) is the estimate that tells you how far to reach; problem 7 in solutions/public/p0007/ sizes its sieve exactly this way. The same law tells you roughly how many primes, semiprimes, or smooth numbers live below a bound — the density argument behind problems like 187 (counting semiprimes) and 304 (walking the primes just past $10^{16}$, whose spacing near $n \ln n$ makes a sieve hopeless and a per-candidate test essential). A sharper count replaces $x/\ln x$ with the logarithmic integral $\mathrm{Li}(x) = \int_2^x \mathrm{d}t/\ln t$, which tracks $\pi(x)$ far more closely — and the question of how closely is where the shallow-looking business of counting primes plunges into the deepest water in mathematics.

In a program, $\pi(n)$ for every $n \le N$ is a single cumulative sum over the sieve's boolean array. It is a step function that moves only at a prime. Problem 423 uses that sparseness. It sums, for every $n \le 5 \times 10^7$, a binomial tail truncated at $c \le \pi(n)$. Evaluated directly, that is about $10^{14}$ terms. Pascal's rule links consecutive tails, so moving from $n$ to $n + 1$ costs one correction term, and the cut-off rises by one only when $n + 1$ is prime. The recurrence has a constant multiplier, so it unrolls into a closed sum of independent terms, with the prime indicator selecting where each extra term enters. NumPy then evaluates the whole sum as vector operations.

From counting to the zeta function

The bridge from the discrete, unruly primes to the smooth machinery of analysis is a single identity Euler wrote down in 1737. For a real (later complex) variable $s > 1$, the Riemann zeta function is the sum over all integers

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}.$$

The right-hand side — the Euler product — is unique factorisation restated in analytic form: expand each factor as a geometric series $1 + p^{-s} + p^{-2s} + \cdots$, multiply them out, and every term $n^{-s}$ appears exactly once, because every $n$ has exactly one prime factorisation. That one equals sign carries all the arithmetic of the primes into a single analytic object. Set $s = 1$ and the left side is the divergent harmonic series, so the product over primes must diverge too — which forces infinitely many primes, and even that $\sum 1/p$ diverges: Euler's analytic reproof of Euclid, and the first time the primes were studied as the raw material of a continuous function rather than one at a time.

The Riemann hypothesis

Riemann's 1859 memoir took the decisive step: he extended $\zeta(s)$ from the half-plane $\Re(s) > 1$, where the sum converges, to a single analytic function on the whole complex plane (bar a simple pole at $s = 1$), and discovered that the distribution of the primes is encoded in the zeros of that continuation. The zeta function vanishes at the negative even integers $-2, -4, -6, \dots$ — the "trivial" zeros — and at infinitely many complex points, all lying in the critical strip $0 < \Re(s) < 1$. The Riemann hypothesis is the assertion, still unproven after more than a century and one of the Millennium Prize Problems, that every one of these non-trivial zeros lies exactly on the critical line $\Re(s) = \tfrac12$.

Why should an engineer counting primes care where a complex function happens to vanish? Because of Riemann's explicit formula, which writes $\pi(x)$ — the jagged prime staircase — as the smooth term $\mathrm{Li}(x)$ minus a sum of correction waves, one per zero $\rho$ of the zeta function:

$$\pi(x) \approx \mathrm{Li}(x) - \sum_{\rho} \mathrm{Li}(x^{\rho}).$$

Each zero $\rho = \beta + i\gamma$ contributes an oscillation whose amplitude is governed by its real part $\beta$ and whose frequency is its imaginary part $\gamma$ — the zeros are literally the harmonics of the primes, which is why the subject is often called the "music of the primes". The Riemann hypothesis says every one of these waves has the same real part $\tfrac12$, so none of them grows faster than $\sqrt{x}$, and the error in the prime number theorem is as small as it could possibly be:

$$\bigl|\pi(x) - \mathrm{Li}(x)\bigr| = O\!\left(\sqrt{x}\,\ln x\right).$$

A single off-line zero would let one correction wave swell out of proportion and the primes would cluster more erratically than anyone has ever observed. So the hypothesis is not idle: it is the precise statement that the primes are distributed as regularly as possible, and a vast body of number theory — sharp bounds on prime gaps, the reliability of fast primality tests, the running time of factorisation algorithms — is proved conditionally on it, waiting for a proof. It also warns against trusting small data: $\mathrm{Li}(x)$ overshoots $\pi(x)$ for every $x$ anyone has ever computed, yet Littlewood proved the difference changes sign infinitely often, the first crossing hiding somewhere near the almost unimaginable Skewes bound — a standing reminder that an asymptotic law is not a promise about the numbers you can reach.

The hypothesis has an equivalent form an engineer can watch happening. The Mertens function $M(x) = \sum_{k \le x} \mu(k)$ adds up the Möbius function ($\pm 1$ for a squarefree $k$ by the parity of its prime count, $0$ otherwise). The Riemann hypothesis is true exactly when $M(x) = O(x^{1/2 + \varepsilon})$ for every $\varepsilon > 0$: the signs of the squarefree numbers must cancel like coin flips. Problem 464 depends on that cancellation without needing it proved. Up to $2 \times 10^7$, $M(x)$ never leaves a band about $\pm 1500$ wide. So a Fenwick tree indexed by Mertens value needs only a few thousand slots, not one per integer.

Order inside the randomness

The tension between local chaos and global law runs right through the open problems. The gaps between consecutive primes average $\ln p$ by the prime number theorem, yet Bertrand's postulate guarantees one always falls before $2p$, prime "deserts" of arbitrary length exist (the run $n! + 2, \dots, n! + n$ is all composite), and the twin prime conjecture — that $p$ and $p + 2$ are both prime infinitely often — remains open even though Zhang's 2013 breakthrough proved some bounded gap recurs forever. Goldbach's conjecture (every even number $> 2$ is a sum of two primes) is another century-old statement about additive structure that the multiplicative theory has never cracked. Project Euler mines exactly this seam: problem 46 tests Goldbach's other conjecture, problem 196 hunts twin- and triplet-prime neighbourhoods, and problem 50 chases the longest run of consecutive primes that sums to a prime — each a small window onto the same theme, that the primes are random enough to be endlessly surprising and structured enough that the surprises obey laws.

Sometimes the primes are not a sequence at all but the vertices of a graph. Problem 425 joins two primes when one becomes the other by changing a single digit or by prepending one. It then asks which primes $P$ can be reached from $2$ by a chain that never passes a prime larger than $P$. That is a bottleneck-path question, and the cap is the very vertex being tested. So I add the primes in increasing order and merge components with a union–find structure. Once $P$ arrives, the graph present is exactly the one on the primes $\le P$, and $P$ qualifies when it shares a root with $2$. That is Kruskal's algorithm with each edge weighted by its larger endpoint. The increasing order the sieve already provides does all the work.

Residue classes obey a law too. Dirichlet's theorem says the primes split evenly among the $\varphi(q)$ residue classes modulo $q$ that are coprime to $q$. Problem 421 sorts the $5.76$ million primes below $10^8$ by whether $p \equiv 1 \pmod 3$ and whether $p \equiv 1 \pmod 5$. The four classes come out at $\tfrac38, \tfrac38, \tfrac18, \tfrac18$ of the total, matching the prediction to three digits. That regularity is useful: it lets you estimate the answer's magnitude before writing the program, and here the estimate showed the sum would land just under the 64-bit ceiling.

Divisibility by different primes is independent as well, and that lets me treat a random integer as a probability model. By the Chinese Remainder Theorem, the multiples of distinct primes are independent events in the limit, in the sense of natural density. So the integers whose smallest prime factor is $p$ have density $\frac{1}{p} \prod_{q < p} (1 - 1/q)$. Problem 779 averages a function of that smallest prime and its exponent over all integers, so the average is an expected value. Given $p$, the exponent beyond the first is geometric with mean $1/(p - 1)$. The problem's infinite sum over $K$ is a geometric series, and because every term is positive I can take it first. What remains is one series over the primes, with terms falling like $1/p^3$, so stopping at a bound $P$ costs less than $1/(2P^2)$. A single running product, updated as the primes go past, evaluates it. Mertens' third theorem says that product shrinks like $e^{-\gamma}/\ln p$, and this is also where the independence stops. Applied to every prime up to $\sqrt x$, it would predict a prime density of $2e^{-\gamma}/\ln x \approx 1.12/\ln x$, which is 12% above what the prime number theorem says. Independence holds for a fixed set of primes as $N \to \infty$, not for a set that grows with $N$. Problem 779 is safe because each term fixes $p$ first, and the large primes carry almost no weight.

Generating and testing primes

Knowing what the primes are is one thing; getting the ones you need into a program is another, and a prime-heavy problem almost always reduces to one of three questions — give me every prime up to a bound, is this one number prime, or what are the prime factors of this number. Each has its own right tool, and reaching for the wrong one is the usual reason a prime solution is slow.

Enumerate every prime up to $N$ — the Sieve of Eratosthenes. Write down every integer from $2$ to $N$; walk the list, and each time you meet a number still standing, cross out all of its multiples. What survives is exactly the primes. Two observations make it fast: start crossing out from $p^2$ (every smaller multiple of $p$ already carries a smaller factor), and stop once $p^2 > N$. The whole pass runs in $O(N \log \log N)$ — very nearly linear — so whenever a problem needs all the primes below a known ceiling, the sieve is almost always the answer. In solutions/public/p0010/ the core is three lines of bytearray strided assignment:

sieve = bytearray(b"\x01") * (max_num + 1)
sieve[0] = sieve[1] = 0
for i in range(2, int(max_num ** 0.5) + 1):
    if sieve[i]:
        sieve[i * i:: i] = bytearray(len(range(i * i, max_num + 1, i)))

The subtlety the sieve carries is the bound. You often want "the first $n$ primes" rather than "primes below $N$", and must size the array before you know where the $n$-th prime lands — which is exactly where the prime number theorem above earns its keep: $p_n \sim n \ln n$, so sieving up to $n \ln n$ (with a small margin) suffices, the ceiling problem 7 uses to reach the 10 001st prime. When even that range will not fit in memory, a segmented sieve processes the interval in cache-sized windows, and an incremental sieve — a generator keyed on each prime's next multiple — yields primes endlessly with no ceiling fixed in advance. Variants trade the same idea around: the Sieve of Sundaram sieves odd numbers through a different indexing, and a linear sieve crosses each composite off exactly once (via its smallest prime factor), handing you a factorisation table as a by-product — useful when a problem needs the least prime factor of every $n \le N$, not just a primality flag.

Several practical points follow from the problems below. Storing odd numbers only halves the array. Problem 315 sieves to $2 \times 10^8$ that way, in 100 MB rather than 200 MB. When the answer's location is unknown, process consecutive fixed-size windows until one contains it. Problem 256 runs a divisor-style sieve over $2^{24}$-wide windows of areas for this reason. Size the sieve to the structure, not the problem's headline bound. Problem 272 needs primes only up to $10^{11}$ divided by the smallest product of four admissible factors, which is a few million. Problem 245 needs primes only to $\sqrt N$, because only the smaller factors are enumerated. And sometimes the sieve's only output is a count. Problem 239 needs nothing but $\pi(100) = 25$, because its derangement formula treats every prime the same, so their values cancel out of the argument. Problem 249 sieves the sums of prime subsets, up to the total of all primes below $5000$, about $1.5$ million, to know which totals are prime. When only a window is needed, generate just that window. Problem 492 wants the primes in $[10^9, 10^9 + 10^7]$. primesieve writes them straight into a NumPy array, and every later per-prime step is one vector operation over all $482\,449$ of them. When how many primes you need depends on the output, double the bound until it is enough. Problem 946 feeds consecutive primes in as run lengths of a continued fraction, and it cannot tell in advance how many runs will produce $10^8$ output terms. When the sieve must classify every $d$ below a bound, as squarefree or not and by its count of distinct primes, the primes up to $\sqrt N$ are enough. A $d \le N$ has at most one prime factor above $\sqrt N$. So the sieve also tracks the product of the small primes it found in each $d$. If that product falls short of $d$, exactly one large prime is missing, and one comparison accounts for it. Problems 632 and 754 sieve $10^8$ values this way with 1229 primes instead of 5.76 million, which matters in NumPy, where every prime costs one slice operation. When the sieve counts divisors rather than primes, count them in pairs. Problem 485 needs $d(n)$ for every $n \le 10^8$. Each divisor $e$ of $n$ pairs with $n/e$, and one of the two is at most $\sqrt n$. So only $i \le \sqrt N$ need visit their multiples, adding $2$ beyond $i^2$ and $1$ at $i^2$ itself. That is $10^4$ slice operations rather than $10^8$. The largest value is known in advance too, set by a highly composite number, and it fits in 16 bits, which keeps the whole table at 200 MB.

Factor a polynomial's values together. Problem 659 needs the largest prime factor of $4k^2 + 1$ for every $k \le 10^7$, values up to $4 \times 10^{14}$. Factoring each value by trial division would take about $10^{14}$ steps. But a prime divides $f(k)$ only along fixed residue classes of $k$, the roots of $f$ modulo $p$. So each prime is sieved along its own progressions, exactly as Eratosthenes sieves along multiples. For $f(k) = (2k)^2 + 1$, the roots exist only when $-1$ is a quadratic residue, so $p \equiv 1 \pmod 4$. Each such prime then has exactly two roots, and Hensel's lemma lifts each root to the progression of $p^2$, $p^3$, and so on. A size bound turns the partial sieve into a complete factorisation. Once every prime up to $2N + 1$ is divided out, the cofactor is either $1$ or a single prime, because two primes above $2N + 1$ multiply to more than any $f(k)$. So the leftover needs no primality test at all: the bound already proves it is prime.

The same walk answers primality when factors are not wanted. Problem 291 begins as a Diophantine equation in two variables. Factoring both sides and dividing out the gcd reduces it to one family, the primes of the form $f(n) = n^2 + (n + 1)^2$ below $L = 5 \times 10^{15}$. (Problem 216 asks the same of $2n^2 - 1$.) Since $2f(n) = (2n + 1)^2 + 1$, only primes $q \equiv 1 \pmod 4$ divide any value, and each strikes two residue classes of $n$. The array is indexed by $n$, not by the value, so about $5 \times 10^7$ cells stand for numbers up to $L$. A composite value has a prime factor at most $\sqrt L$, so anything that survives every such $q$ is prime. Two details separate this from the ordinary sieve. Each prime needs a root first, and for $-1$ there is a closed form: if $a$ is a non-residue, then $a^{(q-1)/4}$ squares to $-1$ by Euler's criterion, so the general square-root algorithm is not needed. And a value equal to $q$ itself must survive, so its class starts one step later, just as Eratosthenes leaves $p$ standing while it crosses off the multiples.

Count without listing — sublinear summatory functions. Some problems need a sum over every $n \le 10^{10}$, such as $\sum \varphi(n)$ or $\sum \mu(n)$, and no sieve reaches that far. The way out is a convolution identity that holds for every $v$: $\sum_{d \le v} \Phi(\lfloor v/d \rfloor) = v(v+1)/2$ for the totient sum $\Phi$, and $\sum_{d \le v} M(\lfloor v/d \rfloor) = 1$ for Mertens. Solved for the $d = 1$ term, each identity becomes a recursion that only ever evaluates the function at the $O(\sqrt v)$ distinct quotients $\lfloor v/d \rfloor$. Sieve directly up to $v^{2/3}$, recurse above that, and the cost balances at $O(v^{2/3})$. Problem 351 uses this for the totient sum at $10^8$. Problem 319 uses it for Mertens at $10^{10}$: it counts distinct real roots $m^{1/i}$, and the Möbius function is just inclusion–exclusion over the primes dividing the exponent. Problem 512 shows what the quotient set buys beyond the one total. It needs $\sum \varphi(n)$ over odd $n \le 5 \times 10^8$ only. Because $\varphi(2m)$ is $\varphi(m)$ or $2\varphi(m)$ by the parity of $m$, the odd sum unrolls to $\Phi(N) - \sum_{k \ge 1} \Phi(\lfloor N/2^k \rfloor)$. Every one of those arguments is already in the quotient set, so the restriction costs $\log_2 N$ lookups. A gcd sum also leads into this recursion. In problem 625, the $i \le j$ with $\gcd(i, j) = d$ number $\varphi(j/d)$. Swapping the order of summation turns $\sum \gcd(i, j)$ into $\sum_k \varphi(k)\, T(\lfloor N/k \rfloor)$, which is a totient sum grouped by quotient.

The recursion is not limited to $\varphi$ and $\mu$. It needs a function $f$ and a partner $g$ such that both $g$ and $f * g$ have prefix sums in closed form, and a completely multiplicative twist keeps that true. Problem 994 weights its gcd sum by $(m - a)(n - b)$, so on each quotient block the summand is a quadratic in $d$. It therefore needs $\Phi_k(x) = \sum_{d \le x} d^k \varphi(d)$ for $k = 0, 1, 2$. Twisting both sides of $\varphi * 1 = \mathrm{id}$ by $\mathrm{id}^k$ gives $\sum_{d \mid n} d^k \varphi(d)\,(n/d)^k = n^{k+1}$, a power sum, and the same recursion follows. Problem 935 counts coprime pairs split by one coordinate's residue modulo $4$. A common divisor divisible by $4$ has $\mu = 0$, and one that is twice an odd number only flips the sign, so every term becomes a Möbius sum over odd integers. The odd indicator $\chi_0$ is completely multiplicative, so $(\mu\chi_0) * \chi_0 = \varepsilon$, and the Mertens recursion runs over odd quotients alone, still in $O(N^{2/3})$.

The same quotient set counts the primes themselves. The Lucy_Hedgehog sieve, a lightweight cousin of the Meissel–Lehmer algorithm, starts with $S(v) = v - 1$ at each of the roughly $2\sqrt N$ stored values. Then, for each prime $p \le \sqrt N$, it removes the numbers whose smallest prime factor is $p$: $S(v) \mathrel{-}= S(\lfloor v/p \rfloor) - S(p - 1)$ for every $v \ge p^2$. After the last prime, $S(v) = \pi(v)$ at every stored point, in $O(N^{3/4})$ time and $O(\sqrt N)$ memory. That is $\pi(10^{10})$ without a ten-billion-cell sieve. Problem 668 needs exactly that. A number fails square-root smoothness when it is $p \cdot m$ with $p$ its largest prime and $m \le p$. So the failures number $\sum_{p \le \sqrt N} p + \sum_{p > \sqrt N} \lfloor N/p \rfloor$, and the second sum regroups into differences of $\pi$ at the quotients. The Min_25 sieve generalises the idea to any multiplicative function whose value on primes is a low-degree polynomial in $p$. Problem 452 counts ordered tuples with product at most $10^9$, which is the summatory function of the $n$-fold divisor function $d_n$. That function equals the constant $n$ on every prime, so the primes contribute $n \cdot \pi(m)$. A recursion over smallest prime factors adds the composites.

Lucy_Hedgehog's intermediate tables carry information too, because step $p$ strikes exactly the numbers whose smallest prime factor is $p$. Problem 521 sums the smallest prime factor of every $n \le 10^{12}$. A prime contributes itself. A composite is $p \cdot m$, with $p \le \sqrt N$ its smallest prime and $m \in [p, \lfloor N/p \rfloor]$ still standing when step $p$ begins. So there are $S(\lfloor N/p \rfloor) - \pi(p - 1)$ such composites, read from the table just before that step updates it, and the total is a by-product of the run. The prime term comes from a second table that starts at $v(v + 1)/2 - 1$ and whose update is scaled by $p$. That scaling is valid because $f(n) = n$ is completely multiplicative. Both updates are linear, so the tables can stay reduced modulo the requested modulus from the start.

Factor or test a single number — trial division. When you have one number, not a range, sieving the whole space below it is wasteful. To factor $n$, divide by $2, 3, 4, \dots$ and peel off each divisor you find; to test primality, divide by candidates up to $\sqrt{n}$ and call it prime if none divide it. The $\sqrt{n}$ cutoff is the crux: a composite $n$ must have a factor no larger than its square root, so nothing above $\sqrt{n}$ can be its smallest factor. A second saving is to divide each factor out completely as you go — then every divisor you meet is automatically prime and needs no separate check. Problem 3 (solutions/public/p0003/) does exactly this, recomputing the $\sqrt{}$-ceiling against the shrinking remainder so the loop ends early once only a large prime cofactor is left. Wheel factorization sharpens the constant: every prime past $2$ is odd and every prime past $3$ is $\equiv \pm 1 \pmod 6$, so stepping through $6k \pm 1$ skips two-thirds of the candidates — it does not change the asymptotics, but on a factoriser's hot loop that factor is worth having.

Test a large single number — the Miller–Rabin primality test. Trial division to $\sqrt{n}$ is fine up to perhaps $10^{12}$; past that its cost explodes. Miller–Rabin instead asks a witness question rooted in Fermat's little theorem: write $n - 1 = 2^s \cdot d$ and check, for a chosen base $a$, whether the repeated squarings of $a^d \pmod n$ betray $n$ as composite. A single base can be fooled, but each independent base that passes multiplies your confidence — and for $n$ below fixed thresholds a specific small set of bases makes the test deterministic, exactly correct with no probability left. Its cost is $O(k \log^3 n)$ for $k$ bases: effectively instant even for numbers with dozens of digits, which is why the higher-numbered primality problems (and RSA key generation) reach for it rather than a sieve.

Split a large composite — Pollard's rho. Miller–Rabin can say that a number is composite, but it gives no factor. Rho iterates $x \mapsto x^2 + c \pmod n$. Modulo an unknown prime factor $p$ the walk repeats after about $\sqrt p$ steps, and a gcd of differences with $n$ catches that repeat without knowing $p$. The expected cost is about $n^{1/4}$, against $\sqrt n$ for trial division. A complete factoriser strips the small primes by trial division, stops on anything Miller–Rabin calls prime, and otherwise splits with rho and recurses. Problem 955 needs one at every step of a walk. Triangular numbers in its sequence are linked by $t(x) + t(j) = t(y)$, which rearranges to $x(x + 1) = ab$. The next one comes from the factor pair of opposite parity that lies closest to the trivial pair $x \cdot (x + 1)$. Consecutive integers are coprime, so I factor $x$ and $x + 1$ separately and merge the results, and the much larger product is never factored at all.

The most common pattern in the problems is a hybrid: sieve the small primes, and run Miller–Rabin on the large candidates a search constructs. Problem 245 sieves only to $\sqrt N$, then tests each solved-for largest prime $q$, which can reach $N/3$. Problem 248 tests $d + 1$ for each divisor $d$ of its target, with candidates beyond $3 \times 10^9$. Problem 516 tests $h + 1$ for each of its few thousand Hamming numbers $h$, up to $10^{12}$. Sieving that far to check a few thousand numbers would be the single-number mistake on a large scale.

Arithmetic modulo a prime

A prime modulus is more than a convenient reduction. The nonzero residues modulo $p$ form a cyclic group of order $p - 1$, and that one structural fact answers a whole class of counting questions in constant time:

How many solutions does $x^k \equiv 1 \pmod p$ have? Exactly $\gcd(k, p - 1)$, because a cyclic group of order $m$ has one subgroup of each order dividing $m$. Problem 421 is the clearest example. It asks for the prime factors below $10^8$ of $n^{15} + 1$ for $10^{11}$ values of $n$, and it becomes tractable once the sum is reordered to run over primes: each prime $p$ divides $n^{15} + 1$ for exactly $\gcd(15, p - 1)$ residues of $n$, and each residue class is counted with a single floor division. The reordering also shows why every such number is composite: the residue $-1$ is always a root.
Glue prime powers together with CRT. Problem 272 counts cube roots of unity modulo $n$. By the Chinese Remainder Theorem the count is multiplicative. Each prime $p \equiv 1 \pmod 3$ contributes a factor $3$, and so does the prime $3$ when $9 \mid n$; every other prime contributes $1$. So "exactly $242$ roots besides $1$" becomes "exactly five such factors", and the rest is a pruned enumeration.
Consecutive integers split the prime powers. Problem 407 wants the largest $a < n$ with $a^2 \equiv a \pmod n$. That means $n \mid a(a - 1)$, and $a$ and $a - 1$ are coprime, so each prime power of $n$ divides one side entirely. Every unitary split $n = d e$ yields one idempotent by CRT, $2^{\omega(n)}$ in all. The search over $a$ for every $n \le 10^7$ becomes a sweep over coprime pairs $(d, e)$ with $de \le N$. The smaller factor is at most $\sqrt N$, so inverting modulo it lets one table of inverses serve every partner.
Binomials and inverses. Modulo a prime, Lucas's theorem computes $\binom{n}{k}$ digit by digit in base $p$. Problem 365 reduces a coefficient with nine billion digits to one residue per prime, then recombines triples of primes by CRT. Every inverse it needs factors into pairwise inverses, $(qr)^{-1}_p = q^{-1}_p r^{-1}_p$. Problem 274's divisibility multiplier is just $10^{-1} \bmod p$, and it has a closed form that depends only on $p$'s last digit, so no Euclid call is needed. When many binomials share one prime, as the two million terms of problem 517 do modulo $10^9 + 7$, build the factorials once. Then take a single Fermat inverse $N!^{\,p-2}$ and run $(k-1)!^{-1} = k \cdot k!^{-1}$ downwards. That is one exponentiation in place of $N$ separate inversions.
Orders divide $p - 1$, or $p + 1$. Fermat's little theorem bounds the order of a nonzero residue by $p - 1$, so a huge exponent can be reduced modulo the group order. Problems 492 and 752 need the same reduction for a quadratic irrational: a root $\alpha$ of $t^2 - 11t + 1$ in 492, and the unit $1 + \sqrt 7$ in 752. Whether $\alpha$ exists in $\mathbb{F}_p$ depends on whether the discriminant is a quadratic residue modulo $p$. If it is (the prime splits), the order divides $p - 1$. If not (the prime is inert), $\alpha$ lives in $\mathbb{F}_{p^2}$. There the Frobenius map $y \mapsto y^p$ is conjugation, so $\alpha^{p+1} = \alpha \bar\alpha$ is the norm, which lies in $\mathbb{F}_p$ again. The norm is $1$ in problem 492, so the order divides $p + 1$, and an exponent of $2^{10^{15} - 1}$ shrinks to a residue modulo $p \mp 1$. Quadratic reciprocity turns the split-or-inert test into a lookup of $p \bmod 13$. In problem 752 the norm is $-6$. So the order of $-6$ in $\mathbb{F}_p$ divides the order, and what remains is an order dividing $p + 1$. A composite modulus then splits by CRT: the order is the lcm of the orders at the prime powers. Going from $p^{k-1}$ to $p^k$ either keeps the order or multiplies it by exactly $p$, because every element of the reduction kernel has order dividing $p$. One test per level decides which. The primes that divide the discriminant or the norm ($2$, $3$, $7$ in 752) are the exceptions, and each needs its own case.
Test a primitive root through the factors of $p - 1$, and keep the root formal. A residue $r$ is a primitive root of $p$ exactly when $r^{(p-1)/q} \ne 1$ for every prime $q \mid p - 1$, because any smaller order divides one of those exponents. Problem 437 asks which primes have a primitive root that satisfies $x^2 \equiv x + 1$. Roots exist only when $5$ is a quadratic residue, and finding them would take a modular square root for each of nearly three million primes. I never find them. In the ring $\mathbb{Z}_p[x]/(x^2 - x - 1)$ every power reduces to $x^m = ax + b$, where $a$ and $b$ are the Fibonacci numbers $F_m$ and $F_{m-1}$ modulo $p$, and those coefficients hold for both roots at once. So one ring power tests both. If $a \ne 0$, then $ar + b = 1$ has one solution, so at most one root fails on that $q$. If $a = 0$, both fail or neither does. For $p = 11$, $x^5 = 5x + 3$ equals $1$ at the root $4$ but not at the root $8$. This is the ring of problems 492 and 752 at a split prime, where it is two copies of $\mathbb{F}_p$ rather than a field, and the formal root stands for both.
Residuosity restricts which primes can divide a polynomial. In problem 245, $4(x^2 - x + 1) = (2x - 1)^2 + 3$. So a prime can divide $x^2 - x + 1$ only if $-3$ is a quadratic residue modulo it, which means $p = 3$ or $p \equiv 1 \pmod 3$. Half the candidate moduli disappear before the search starts.
Solve a quadratic modulo $p^2$ one prime at a time. Problem 457 wants, for every prime up to $10^7$, the least $n$ with $p^2 \mid n^2 - 3n - 1$. A scan up to $p^2$ is impossible. Completing the square gives $(2n - 3)^2 \equiv 13$, so the problem becomes a modular square root. One exists only when $(13/p) = 1$, and because $13 \equiv 1 \pmod 4$, reciprocity reduces that test to looking up $p \bmod 13$. The Tonelli–Shanks algorithm finds the root. For the half of the primes with $p \equiv 3 \pmod 4$ it is the single power $13^{(p+1)/4}$. A simple root then lifts to $p^2$ in one Newton step of Hensel's lemma. The primes that divide $2$ or the discriminant $13$ are the exceptions again, and each turns out to have no solution.
The order of $2$ restricts the prime factors of $2^n - 1$. If $q \mid 2^n - 1$, the order of $2$ modulo $q$ divides both $n$ and $q - 1$. When $n$ is prime that order is $n$, so every prime factor of $2^n - 1$ is $\equiv 1 \pmod n$. Problem 605 needs a fraction with $(2^n - 1)^2$ in the denominator and $n \approx 10^8$ reduced to lowest terms. The power has thirty million digits. But the numerator is $\equiv n$ modulo $2^n - 1$, so any common prime divides $\gcd(n, 2^n - 1)$, which needs only $2^n \bmod n$. When the common factor $g$ is not invertible modulo the output modulus $M$, I compute modulo $M g^2$ and divide the residue exactly by $g^2$.
A prime modulus makes every non-trivial root of unity primitive. A roots-of-unity filter keeps the terms of a generating function whose exponent is divisible by $n$: substitute each $n$-th root $\omega^j$ and average. Problem 635 counts the $p$-element subsets of $\{1, \dots, qp\}$ whose sum is divisible by $p$. For a general $n$ the $n$ filter terms are all different. For a prime they collapse. Every $\omega^j$ with $j \ne 0$ is again primitive, so as $k$ runs to $qp$ the powers $\omega^{jk}$ visit each root exactly $q$ times, and all $p - 1$ non-trivial terms are equal. Each works out to $q$, so the count is a binomial coefficient plus a small correction, divided by $p$. The remaining work is that binomial modulo $10^9 + 9$ for 5.76 million primes. One running scan of factorials, stopping at every point that is needed, serves all of them. All the inverses together then cost one vectorised Fermat exponentiation.
Exponential sums at a prime have a known size. Problem 875 counts the zeros modulo $n$ of a quadratic form in eight variables. The same filter turns the count into a sum of eighth powers of quadratic Gauss sums $G = \sum_x e(t x^2 / n)$. Their values are erratic, but their modulus is not: $|G|^2 = m$ for every odd modulus $m$ and every unit $t$. So the count becomes a Dirichlet convolution of two simple multiplicative functions, and the problem reduces to a totient sieve. At an odd prime it gives the classical $p^7 + p^4 - p^3$. The prime $2$ is the exception, as it so often is: the Gauss sum vanishes modulo $2$ and is larger at higher powers of $2$, and that case needs its own correction factor.
A power residue symbol projects a map onto cosets. When $5 \mid p - 1$, Fermat makes $\chi(x) = x^{(p-1)/5}$ a fifth root of unity. This is the power residue symbol, the fifth-power analogue of Euler's criterion, and it labels each nonzero residue by its coset of the subgroup of fifth powers. Problem 971 iterates $x \mapsto x(1 + \chi(x))$ modulo $p$ and counts periodic points. The multiplier depends only on the coset, so the functional graph on $p$ points projects onto a map on five cosets. A coset on a cycle of length $L$ comes back multiplied by one fixed unit. Multiplication by a unit is a bijection, so every element of that coset is periodic, and a coset off the cycle holds no periodic point. Each prime then costs a few modular exponentiations, not a walk over $p$ points.
A cyclotomic divisibility is a factorisation of the group. Problem 995 wants the least $s$ for which $1 + x + \dots + x^{p-1}$ divides $1 + \sum_{d \mid s} x^d$. That polynomial is the cyclotomic polynomial $\Phi_p$, which is irreducible. So the condition is a vanishing sum at a primitive $p$-th root of unity, and the only relation among those powers is that all $p$ of them sum to zero. That forces the divisors of $s$ to hit every nonzero residue modulo $p$ exactly once. For $S(5) = 8$, the divisors $1, 2, 4, 8$ are $1, 2, 4, 3 \pmod 5$. Divisors of $\prod q_i^{e_i}$ are products of one element from each set $\{1, q_i, \dots, q_i^{e_i}\}$, so those sets factor the cyclic group $(\mathbb{Z}/p)^\times$. Hajós's theorem says one factor of such a factorisation is a subgroup. Applied repeatedly, it turns the factors into a chain of subgroups, one per divisor of $p - 1$, with each exponent fixed by its prime's multiplicative order. The minimum becomes a shortest path over the divisors of $p - 1$, and only the least prime of each order matters. $S(p)$ itself is far too large to build, so I add logarithms along the path and never form it.

The same structure, at cryptographic sizes, is what the next section turns into a lever.

The asymmetry that pays the modern bills

Here is the fact the applications turn on: multiplying primes is easy, and factoring their product is hard. Given two large primes you can multiply them in microseconds, but given only the product — a semiprime $n = pq$ — recovering $p$ and $q$ is, as far as anyone knows, infeasible once the primes are a few hundred digits long. No polynomial-time integer-factorisation algorithm is known (on classical hardware), yet checking primality is cheap. That gap between an easy forward operation and an intractable inverse is a one-way function, and it is the engine of modern public-key cryptography:

RSA. A public key is a semiprime $n = pq$ built from two secret large primes. Encryption and decryption are modular exponentiations whose correctness is guaranteed by Fermat's and Euler's theorems — you work in the exponent modulo $\varphi(n) = (p-1)(q-1)$ — and the scheme is secure precisely because an attacker who cannot factor $n$ cannot recover $\varphi(n)$. Generating the keys means manufacturing large primes, which is where fast probabilistic primality tests earn their keep.
Diffie–Hellman and the discrete logarithm. Arithmetic modulo a large prime $p$ forms a cyclic group; exponentiating a generator is easy but inverting it (the discrete log) is hard, giving a second one-way function that underlies key exchange and signatures. The same idea over the points of an elliptic curve gives equivalent security with far smaller keys.

The reach of the mathematics goes well past cryptography, because a prime modulus has the cleanest possible arithmetic — the integers modulo $p$ form a finite field, where every non-zero element is invertible:

Hashing. Hash tables size their bucket arrays to a prime and reduce keys modulo it, because a prime shares no factor with the strides that real-world keys tend to arrive on, spreading them evenly instead of piling them into a few buckets. Polynomial "rolling" hashes evaluate a string as a polynomial modulo a large prime for the same reason.
Pseudo-random numbers. The classic linear congruential generator MINSTD uses the Mersenne prime $2^{31} - 1$ as its modulus to attain full period, and the Mersenne Twister — the default generator in Python, and in problem 213's kind of stochastic simulation — takes its name and its period $2^{19937} - 1$ from a Mersenne prime.
Error correction and signal processing. Reed–Solomon codes behind QR codes, CDs, and deep-space links do their arithmetic in a finite field; prime-length fast Fourier transforms exploit the multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ to reindex a transform.

How to reason about it

The through-line across the problems below is that a prime is never just a prime — it is the atom that makes some larger quantity computable:

See a multiplicative quantity — a divisor count, a totient, a coprimality condition, a "product of two primes" — and reach for the factorisation. The exponent vector is the object you actually manipulate; the answer is a product over the primes dividing $n$. When the value is given and $n$ is wanted, search the factorisations of the target (problems 241, 248, 516), not the integers. When each prime's $p - 1$ feeds only smaller primes, place the primes from the largest down, so each one is settled once the search has passed it (problem 342). Over a run of factorials, update the exponents incrementally rather than refactoring (problem 675). When the statistic is linear in the exponents, a per-prime generating function makes the count rational (problem 682). When only the order of the numbers matters, divide out the factor they all share (problem 615). When the question says "exactly $k$" prime factors, count "at least" and invert binomially (problem 632). When it says "coprime to $n$", turn the condition into a Möbius sum over divisors, which sits in the exponent when the quantity is a product (problem 754). When coprime factors multiply to a square, each factor is a square (problem 764). When the generators of a semigroup are coprime, a multiple of one walks every residue class of another (problem 718). With two generators, the gaps form a staircase in which "reachable" is coordinate dominance (problem 988). A ratio in lowest terms forces a square divisor (problem 518). When the condition is divisibility between smooth numbers, think of antichains in exponent space (problem 333). When it is "the product is a square", the parities form a vector over $\mathbb{F}_2$, and the count is a kernel dimension (problem 619). When it depends only on which small primes divide $n$, absorb those primes into one period table and enumerate only the large ones (problem 967).
See a congruence summed over a huge range — and consider reordering the sum to run over the primes. The cyclic group modulo $p$ answers "how many residues" in $O(1)$ (problem 421). CRT multiplies those counts across prime powers (problem 272) and builds one solution per coprime split (problem 407). An exponent too large to write down reduces modulo the group order. That order is $p - 1$, or $p + 1$ for an irrational at an inert prime (problems 492, 752). To test for a primitive root, check the powers $(p - 1)/q$, and if the candidates are the roots of a polynomial, compute in the quotient ring so that one power tests them all (problem 437). When a map's behaviour depends only on a residue's power-residue class, project it onto the cosets (problem 971). When residues must be hit exactly once, as divisors or as products, think of a factorisation of the cyclic group and its chain of subgroups (problem 995). When a filter or an exponential sum appears, ask which property of primality it needs. Every non-trivial root is primitive (problem 635), and a Gauss sum has modulus $\sqrt p$ (problem 875). A quadratic modulo $p^2$ is a square root modulo $p$ followed by a Hensel lift (problem 457). A number too large to write down, such as $2^n - 1$, still has prime factors constrained by the order of $2$ (problem 605).
Need the factors of a whole family of values — the values of a polynomial, or every $d$ below a bound — and sieve along residue classes rather than factoring one value at a time. Each prime acts only on its roots, lifted by Hensel to its powers. A size bound then certifies the cofactor as $1$ or a prime (problem 659). If only primality is wanted, index the array by $n$ and strike with primes up to the square root of the largest value (problems 216, 291). Primes up to $\sqrt N$, plus a product check, account for the one possible large factor (problems 632, 754). Divisor counts need only $\sqrt N$ strides, because divisors come in pairs (problem 485).
Need a total over $10^{10}$ or more — $\sum \varphi$, $\sum \mu$, $\pi(x)$ — and a sieve will not reach. Work on the quotient set: the recursion at $O(n^{2/3})$ for $\Phi$ and $M$ (problems 319, 351, 512). A completely multiplicative twist on both sides of the identity extends it to weighted or restricted variants, such as $d^k\varphi(d)$ or $\mu$ on the odd integers (problems 935, 994). For $\pi$ use Lucy_Hedgehog at $O(n^{3/4})$ (problem 668), and for a multiplicative function that is simple on primes use Min_25 (problem 452). When the sum is over smallest prime factors, read the Lucy tables mid-run, since step $p$ strikes exactly those numbers (problem 521).
Need a bound or a density — how many primes below $N$, how large the $n$-th prime, how many semiprimes in a range — and the prime number theorem ($\pi(x) \sim x/\ln x$, $p_n \sim n \ln n$) is your estimate. Use it to size a sieve, not to replace an exact count. When $\pi(n)$ is a parameter for every $n$, it is a cumulative sum of the sieve, and it changes only at primes (problem 423). When an average runs over all integers, treat divisibility by each fixed prime as an independent event and sum over the primes, but do not let the set of primes grow with $N$ (problem 779).
See a one-way structure — a public key, a semiprime to be split, a discrete log — and recognise that its security is the hardness of a prime problem. The Euler problems that touch cryptography (RSA-flavoured factorisation, modular inverses) are miniatures of the same asymmetry.
Then pick the tool by the shape of the question. Many primes below a known bound → sieve, sized to the inputs ($n \ln n$ for "the $n$-th prime") and built inside solve() so the benchmark counts it honestly. Factor one number, or a modest range → trial division to $\sqrt{n}$ with full division-out and a $6k \pm 1$ wheel. A yes/no on one large number → Miller–Rabin with a deterministic base set; a search that builds large candidates from small primes → sieve the small primes and Miller–Rabin the candidates it builds. Factors of a number too large for trial division → Pollard's rho, with Miller–Rabin to stop the recursion (problem 955). The classic mistake is answering a range question one number at a time — a primality test in a loop where a single $O(N \log \log N)$ sieve would produce the whole set — or answering a single-number question with a sieve of millions of primes to check just one.

Match the mathematics and the algorithm to the shape of the question and the erratic surface of the primes gives way to a small set of reliable laws — the same laws that, four centuries after Fermat, keep the world's secrets. The problems below all turn on that fit.

Problems163 / 260

● 0003 — Largest Prime Factor
● 0007 — 10 001st Prime
● 0010 — Summation of Primes
● 0012 — Highly Divisible Triangular Number
● 0023 — Non-Abundant Sums
● 0027 — Quadratic Primes
● 0029 — Distinct Powers
● 0033 — Digit Cancelling Fractions
● 0035 — Circular Primes
● 0037 — Truncatable Primes
● 0041 — Pandigital Prime
● 0046 — Goldbach's Other Conjecture
● 0047 — Distinct Primes Factors
● 0049 — Prime Permutations
● 0050 — Consecutive Prime Sum
● 0051 — Prime Digit Replacements
● 0058 — Spiral Primes
● 0060 — Prime Pair Sets
● 0062 — Cubic Permutations
● 0069 — Totient Maximum
● 0070 — Totient Permutation
● 0071 — Ordered Fractions
● 0072 — Counting Fractions
● 0073 — Counting Fractions in a Range
● 0075 — Singular Integer Right Triangles
● 0077 — Prime Summations
● 0087 — Prime Power Triples
● 0095 — Amicable Chains
● 0097 — Large Non-Mersenne Prime
● 0108 — Diophantine Reciprocals I
● 0110 — Diophantine Reciprocals II
● 0111 — Primes with Runs
● 0118 — Pandigital Prime Sets
● 0123 — Prime Square Remainders
● 0124 — Ordered Radicals
● 0127 — abc-hits
● 0128 — Hexagonal Tile Differences
● 0130 — Composites with Prime Repunit Property
● 0131 — Prime Cube Partnership
● 0132 — Large Repunit Factors
● 0133 — Repunit Nonfactors
● 0134 — Prime Pair Connection
● 0136 — Singleton Difference
● 0141 — Square Progressive Numbers
● 0146 — Investigating a Prime Pattern
● 0152 — Sums of Square Reciprocals
● 0153 — Investigating Gaussian Integers
● 0157 — Base-10 Diophantine Reciprocal
● 0160 — Factorial Trailing Digits
● 0171 — Square Sum of the Digital Squares
● 0179 — Consecutive Positive Divisors
● 0187 — Semiprimes
● 0193 — Squarefree Numbers
● 0196 — Prime Triplets
● 0200 — Prime-proof Squbes
● 0202 — Laserbeam
● 0203 — Squarefree Binomial Coefficients
● 0204 — Generalised Hamming Numbers
● 0211 — Divisor Square Sum
● 0214 — Totient Chains
● 0216 — The Primality of $2n^2 - 1$
● 0221 — Alexandrian Integers
● 0228 — Minkowski Sums
● 0231 — Prime Factorisation of Binomial Coefficients
● 0233 — Lattice Points on a Circle
● 0234 — Semidivisible Numbers
● 0239 — Twenty-two Foolish Primes
● 0241 — Perfection Quotients
● 0243 — Resilience
● 0245 — Coresilience
● 0248 — Euler's Totient Function Equals 13!
● 0249 — Prime Subset Sums
● 0251 — Cardano Triplets
● 0256 — Tatami-Free Rooms
● 0257 — Angular Bisectors
○ 0263 — An Engineers' Dream Come True
○ 0266 — Pseudo Square Root
○ 0268 — At Least Four Distinct Prime Factors Less Than 100
● 0272 — Modular Cubes, Part 2
○ 0273 — Sum of Squares
● 0274 — Divisibility Multipliers
○ 0278 — Linear Combinations of Semiprimes
● 0288 — An Enormous Factorial
● 0291 — Panaitopol Primes
● 0293 — Pseudo-Fortunate Numbers
○ 0302 — Strong Achilles Numbers
● 0304 — Primonacci
○ 0308 — An Amazing Prime-generating Automaton
● 0313 — Sliding Game
● 0315 — Digital Root Clocks
● 0319 — Bounded Sequences
○ 0320 — Factorials Divisible by a Huge Integer
○ 0329 — Prime Frog
● 0333 — Special Partitions
● 0342 — The Totient of a Square Is a Cube
● 0347 — Largest Integer Divisible by Two Primes
● 0351 — Hexagonal Orchards
○ 0355 — Maximal Coprime Subset
● 0357 — Prime Generating Integers
○ 0362 — Squarefree Factors
● 0365 — A Huge Binomial Coefficient
● 0381 — $(\text{prime}-k)$ Factorial
○ 0386 — Maximum Length of an Antichain
● 0387 — Harshad Numbers
○ 0388 — Distinct Lines
○ 0399 — Squarefree Fibonacci Numbers
● 0407 — Idempotents
○ 0418 — Factorisation Triples
● 0420 — $2 \times 2$ Positive Integer Matrix
● 0421 — Prime Factors of $n^{15}+1$
● 0423 — Consecutive Die Throws
● 0425 — Prime Connection
● 0429 — Sum of Squares of Unitary Divisors
● 0437 — Fibonacci Primitive Roots
○ 0441 — The Inverse Summation of Coprime Couples
○ 0446 — Retractions B
○ 0451 — Modular Inverses
● 0452 — Long Products
● 0457 — A Polynomial Modulo the Square of a Prime
● 0464 — Möbius Function and Intervals
○ 0467 — Superinteger
○ 0468 — Smooth Divisors of Binomial Coefficients
● 0478 — Mixtures
● 0484 — Arithmetic Derivative
● 0485 — Maximum Number of Divisors
● 0487 — Sums of Power Sums
● 0492 — Exploding Sequence
○ 0495 — Writing $n$ as the Product of $k$ Distinct Positive Integers
○ 0500 — Problem 500!!!
● 0501 — Eight Divisors
● 0510 — Tangent Circles
● 0512 — Sums of Totients of Powers
○ 0515 — Dissonant Numbers
● 0516 — $5$-smooth Totients
● 0517 — A Real Recursion
● 0518 — Prime Triples and Geometric Sequences
● 0521 — Smallest Prime Factor
○ 0526 — Largest Prime Factors of Consecutive Numbers
○ 0533 — Minimum Values of the Carmichael Function
○ 0536 — Modulo Power Identity
○ 0537 — Counting Tuples
○ 0540 — Counting Primitive Pythagorean Triples
○ 0541 — Divisibility of Harmonic Number Denominators
○ 0543 — Prime-Sum Numbers
● 0545 — Faulhaber's Formulas
○ 0548 — Gozinta Chains
● 0549 — Divisibility of Factorials
○ 0552 — Chinese Leftovers II
○ 0556 — Squarefree Gaussian Integers
○ 0560 — Coprime Nim
○ 0563 — Robot Welders
● 0565 — Divisibility of Sum of Divisors
○ 0569 — Prime Mountain Range
○ 0574 — Verifying Primes
○ 0578 — Integers with Decreasing Prime Powers
○ 0580 — Squarefree Hilbert Numbers
○ 0590 — Sets with a Given Least Common Multiple
○ 0592 — Factorial Trailing Digits 2
○ 0593 — Fleeting Medians
○ 0598 — Split Divisibilities
○ 0603 — Substring Sums of Prime Concatenations
● 0605 — Pairwise Coin-Tossing Game
○ 0606 — Gozinta Chains II
○ 0609 — $\pi$ Sequences
● 0615 — The Millionth Number with at Least One Million Prime Factors
○ 0616 — Creative Numbers
○ 0618 — Numbers with a Given Prime Factor Sum
● 0619 — Square Subsets
● 0625 — Gcd Sum
○ 0627 — Counting Products
● 0632 — Square Prime Factors
○ 0633 — Square Prime Factors II
○ 0634 — Numbers of the Form $a^2b^3$
● 0635 — Subset Sums
○ 0636 — Restricted Factorisations
○ 0639 — Summing a Multiplicative Function
● 0642 — Sum of Largest Prime Factors
○ 0643 — $2$-Friendly
○ 0646 — Bounded Divisors
● 0650 — Divisors of Binomial Product
○ 0652 — Distinct Values of a Proto-logarithmic Function
● 0659 — Largest Prime
● 0668 — Square Root Smooth Numbers
● 0675 — $2^{\omega(n)}$
● 0678 — Fermat-like Equations
● 0682 — $5$-Smooth Pairs
○ 0687 — Shuffling Cards
● 0694 — Cube-full Divisors
○ 0699 — Triffle Numbers
● 0705 — Total Inversion Count of Divided Sequences
○ 0708 — Twos Are All You Need
○ 0712 — Exponent Difference
○ 0717 — Summation of a Modular Formula
● 0718 — Unreachable Numbers
○ 0727 — Triangle of Circular Arcs
○ 0730 — Shifted Pythagorean Triples
○ 0734 — A Bit of Prime
○ 0738 — Counting Ordered Factorisations
● 0745 — Sum of Squares II
○ 0748 — Upside Down Diophantine Equation
● 0752 — Powers of $1+\sqrt 7$
○ 0753 — Fermat Equation
● 0754 — Product of Gauss Factorials
○ 0758 — Buckets of Water
● 0764 — Asymmetric Diophantine Equation
○ 0769 — Binary Quadratic Form II
● 0771 — Pseudo Geometric Sequences
● 0772 — Balanceable $k$-bounded Partitions
○ 0773 — Ruff Numbers
○ 0777 — Lissajous Curves
● 0779 — Prime Factor and Exponent
○ 0784 — Reciprocal Pairs
○ 0785 — Symmetric Diophantine Equation
● 0787 — Bézout's Game
● 0800 — Hybrid Integers
○ 0801 — $x^y \equiv y^x$
○ 0805 — Shifted Multiples
● 0808 — Reversible Prime Squares
○ 0810 — XOR-Primes
○ 0817 — Digits in Squares
○ 0821 — 123-Separable
○ 0823 — Factor Shuffle
○ 0826 — Birds on a Wire
● 0829 — Integral Fusion
● 0834 — Add and Divide
○ 0838 — Not Coprime
○ 0840 — Sum of Products
○ 0841 — Regular Star Polygons
● 0845 — Prime Digit Sum
○ 0846 — Magic Bracelets
● 0850 — Fractions of Powers
● 0853 — Pisano Periods 1
○ 0861 — Products of Bi-Unitary Divisors
○ 0869 — Prime Guessing
○ 0874 — Maximal Prime Score
● 0875 — Quadruple Congruence
○ 0881 — Divisor Graph Width
● 0883 — Remarkable Triangles
○ 0886 — Coprime Permutations
○ 0920 — Tau Numbers
● 0926 — Total Roundness
○ 0927 — Prime-ary Tree
● 0932 — $2025$
● 0934 — Unlucky Primes
● 0935 — Rolling Square
○ 0942 — Mersenne's Square Root
● 0946 — Continued Fraction Fraction
○ 0952 — Order Modulo Factorial
○ 0953 — Factorisation Nim
● 0955 — Finding Triangles
○ 0956 — Super Duper Sum
○ 0958 — Euclid's Labour
● 0962 — Angular Bisector and Tangent 2
● 0967 — $B$-Trivisible Numbers
● 0971 — Modular Polynomial Composition
● 0975 — A Winding Path
● 0988 — Non-attacking Frogs
● 0994 — Counting Triangles
● 0995 — A Particular Pair of Polynomials
○ 1005 — Median Prime List