Engineering / Mathematics — The Distribution of Primes
Mertens' Theorem
Mertens' theorems on sums and products over primes, and their role in estimating smoothness probabilities.
Executive summary
Mertens established precise asymptotics for the sum of reciprocals of primes and for the product of terms one minus one over p. Both are elementary consequences of Chebyshev-type estimates.
The product formula is the one that matters computationally: it controls the density of smooth numbers, which is the quantity governing the running time of index calculus and sieve factoring methods.
Learning objectives
- State Mertens' two main asymptotic results.
- Connect the product formula to sieving and smoothness.
- Explain the appearance of the Euler-Mascheroni constant.
01The theorems
Mertens' theorems
Σ_{p ≤ x} (ln p)/p = ln x + O(1)
Σ_{p ≤ x} 1/p = ln ln x + M + o(1), where M is Mertens' constant
∏_{p ≤ x} (1 − 1/p) ~ e^{−γ} / ln x, with γ the Euler–Mascheroni constant
The divergence of the sum of prime reciprocals — at the glacial rate of ln ln x — is itself a strong statement: it implies the infinitude of primes and says the primes are substantially denser than the squares, whose reciprocals converge.
02Sieving and smoothness
The product formula is exactly the proportion of integers surviving a sieve by all primes up to x, which is what makes it central to factoring algorithms.
| Quantity | Estimate | Used in |
|---|---|---|
| Density of integers coprime to all p ≤ y | e^{−γ}/ln y | Sieve of Eratosthenes analysis |
| Density of y-smooth numbers below x | ρ(u), u = ln x/ln y | Index calculus, quadratic sieve |
| Expected smooth candidates per sieve interval | interval length × density | Sieving parameter selection |
The Dickman function ρ(u) governing smooth number density is not elementary, but Mertens' theorem supplies the base case and the calibration constant that make its use accurate.
03Consequences for algorithm tuning
Index calculus and sieve algorithms balance two costs: the time spent finding smooth relations, which falls as the smoothness bound rises, and the time spent solving the resulting linear system, which grows as the bound rises.
- Small factor base
Few relations neededBut smooth numbers are rare; relation collection dominates - Large factor base
Smooth numbers commonBut the linear algebra step dominates - Optimal bound
L(1/2) or L(1/3)Balances the two; derived from smoothness density estimates
04Frequently asked questions
Why does the sum of prime reciprocals diverge so slowly?
Because the primes thin out logarithmically. The density of primes near x is about 1/ln x, so the contribution of primes in [x, 2x] is roughly 1/ln x, and summing over dyadic ranges gives a harmonic-like series in ln x, hence ln ln x.
Is Mertens' constant related to Euler's constant?
They are different constants, though both appear in this circle of ideas and both arise from comparing discrete sums with integrals. Mertens' constant is approximately 0.2615.
Are these theorems elementary?
Yes, in the technical sense of not requiring complex analysis. They follow from Chebyshev-type bounds together with partial summation, and predate the prime number theorem.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 81-85.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.