How many primes a typical number has

One way to factor, and no other proved that every whole number is a product of primes in exactly one way. That makes it meaningful to ask how many primes a number has. Twelve has two different prime factors, 2 and 3; thirty has three; 9,699,690 — the product of the first eight primes — has eight. And a prime has one. The question this essay asks is what is typical: pick a number of a given size at random, and how many different primes divide it?

The answer was found in two stages. In 1917 G. H. Hardy and Srinivasa Ramanujan proved that almost every number $n$ has close to $\log \log n$ distinct prime factors, where the logarithms are natural ones. In 1940 Paul Erdős and Mark Kac proved much more: the count, centred at $\log \log n$ and divided by $\sqrt{\log \log n}$, has a normal distribution in the limit. The number of prime factors of a random number behaves like a sum of many small independent pieces — one for each prime, recording whether that prime divides it — and obeys the central limit theorem that governs a bell curve assembled out of coin flips.

Both theorems are about the limit. This essay counts the prime factors of every number up to ten million and asks how much of either one can be seen.

Three primes, give or take one #

The counts come from a sieve. Walk through the numbers from 2 to ten million; at each number not yet marked by a smaller prime, which is therefore prime, add one to the count of every multiple of it. When the walk finishes, each number’s count is its number of distinct prime factors, written $\omega(n)$, and the whole computation takes a fraction of a second. A few counts are checked by hand: $\omega(360) = 3$, $\omega(1024) = 1$, $\omega(9{,}699{,}690) = 8$.

The distribution in the first figure is lopsided and compact. 6.7% of the numbers up to ten million have one distinct prime factor — the primes and the prime powers — 25.4% have two, 36.4% three, 23.9% four, 6.9% five, and fewer than one in a hundred have six or more. The average is 3.01, and the most common count is the same three: a typical number below ten million is a product of three different primes, possibly with some of them repeated, such as $2 \cdot 7 \cdot 41 = 574$ or $3^2 \cdot 11 \cdot 4{,}583$. The limiting bell, centred at $\log \log 10^7 = 2.78$ with the same number as its variance, puts the peak in about the right place and is far too wide: it predicts seven distinct primes for one number in about a hundred, when the true share is one in nearly six thousand.

That is not a failure of the theorem. A number up to ten million cannot have more than eight distinct prime factors at all, since the product of the first nine primes is over two hundred million, so the count has nowhere to spread to. The limiting bell assumes that every prime up to $n$ contributes its own small, independent chance of dividing $n$, and for numbers of this size the large primes are not independent of one another: a number divisible by a prime near a million has room for only one more prime factor of that size.

The average is right from the start #

Hardy and Ramanujan’s theorem has an easy half, and the next figure shows it working immediately.

The average of $\omega(n)$ over the numbers up to $N$ is the number of pairs (prime $p$, multiple of $p$ up to $N$), divided by $N$. Each prime $p$ has $\lfloor N/p \rfloor$ multiples up to $N$, so the average is close to the sum of $1/p$ over the primes up to $N$ — and that sum is $\log \log N$ plus a constant, $0.2615$, found by Franz Mertens in 1874. The figure’s dots sit on that curve to within a twentieth from a hundred thousand onward. It is the same sum that diverges in the sieve written as a product, there as a proof that the primes are infinite in number and here as the average count of prime factors, and it diverges about as slowly as any sum that diverges at all.

The variance does not follow its formula. The limit says it should be about $\log \log N$, and at ten million it is 1.10 against 2.78, trailing by an amount that is larger than the variance itself and shrinking only slowly. Pál Turán’s proof of the Hardy–Ramanujan theorem in 1934 used exactly this quantity — he showed that the variance is at most a constant times $\log \log N$, so that numbers far from the average are rare — and his bound is true and loose at every size in the figure. The centring is a first-order fact, visible at once; the width is a second-order fact, and the second-order corrections are as large as the thing they correct.

The bell, standardised #

Erdős and Kac’s theorem is a statement about the standardised count, $(\omega(n) - \log \log N)/\sqrt{\log \log N}$, and the figure plots that quantity for four ranges of $N$ against the standard bell.

Each range is only a handful of points, because there are only five or six possible values, and all four ranges look nearly the same: a curve with a tall peak slightly right of centre and thin tails, nothing like the bell. Going from ten thousand to ten million — a thousandfold increase in $N$ — moves $\log \log N$ from 2.22 to 2.78, and the curves hardly change. The rate at which the standardised count approaches the bell was found by Alfréd Rényi and Turán in 1958: the error is of order $1/\sqrt{\log \log N}$. That is the same kind of rate how fast the bell arrives found for sums of independent coin tosses, one over the square root of the number of terms — but here the number of effective terms is $\log \log N$, which is under three.

How large a number must be #

The sizes needed to see the limit can be computed directly, since $\log \log N = k$ means $N = e^{e^k}$.

$\log \log N$ reaches 1 at $N = 15$, 2 at about 1,600, 3 at about $5 \times 10^8$, and 4 at a number with 24 digits. Five needs 65 digits and six needs 176. The largest numbers anyone has factored by general methods have about 250 digits, which puts them between six and seven. A typical number with ten different prime factors is a number with about 9,566 digits, and a central limit theorem whose effective number of terms is ten is still a rough one.

So the Erdős–Kac theorem describes numbers that nobody will ever write down, and the reason is structural rather than computational. The count of prime factors grows with the logarithm of the logarithm, the slowest growth that appears naturally anywhere in arithmetic, and a bell needs many terms to form.

Repeated primes are a small, settled correction #

Counting prime factors with repetition — $\Omega(n)$, for which $12 = 2 \cdot 2 \cdot 3$ has three — changes little, and the next figure shows why.

The difference $\Omega(n) - \omega(n)$ counts the extra copies of primes that divide $n$ more than once. Most numbers have none: the share with no repeated prime is the share not divisible by the square of any prime, and that is $6/\pi^2 \approx 60.8\%$, because a number escapes being divisible by $p^2$ with chance $1 - 1/p^2$ and the product of those chances over all primes is $1/\zeta(2) = 6/\pi^2$. The average of the difference is the sum over primes of $1/(p(p-1))$, about $0.7732$, and the count up to a thousand already gives $0.752$. Repetition is a constant correction, dominated by the small primes, and it has settled long before the distinct count has started to show its limit.

That separation says where the slow behaviour lives. Every prime contributes to $\omega(n)$ with chance about $1/p$ of dividing $n$, and the sum of those chances grows without limit, too slowly to see; the chance of a repeated factor is about $1/p^2$, and the sum of those converges fast. A sum of independent pieces that grows like $\log \log N$ is a central limit theorem with $\log \log N$ terms. A sum that converges is a fixed random correction.

The model the theorems are about #

The heuristic can be run exactly instead of argued. Build a model “random number” by letting every prime up to ten million divide it independently, each with chance one over itself, and count how many primes were chosen. The distribution of that count is the product, over all 664,579 primes up to ten million, of the factors $1 - 1/p + x/p$, read off as coefficients of $x^k$, and it can be computed in one pass.

The model’s average is 3.04, against the true 3.01: the first-order fact survives the model unharmed, as the computation of the average by counting multiples promised it would. Its variance is 2.59 against the true 1.10, and it spreads its counts as widely as the limiting bell does — giving a real chance to nine or more distinct primes, which no number below 223,092,870 can have. The model is the reason the bell has the width it has, and at ten million the model is wrong about exactly the thing that sets the width.

What the model gets wrong is easy to say. In it, a number can be divisible by two primes near five million and by a dozen others at once; among real numbers up to ten million, divisibility by one large prime uses up almost all the room. Real numbers are a product, and a product of large primes is too large to be counted. The independence holds for small primes and fails for large ones, and at reachable sizes the large primes are a large part of the count.

Independence that is only approximate #

The heuristic behind both theorems treats divisibility by different primes as independent events, and for small primes that is exactly right in the limit: among numbers up to $N$, the share divisible by both 2 and 3 is the product of the shares divisible by each. It fails for primes near $N$: no number up to $N$ is divisible by two primes larger than $\sqrt N$, although the independent model allows it. Erdős and Kac’s proof handles this by cutting off at primes up to a small power of $N$, applying the central limit theorem to the truncated sum, and showing that the large primes change the count by an amount that does not matter after dividing by $\sqrt{\log \log N}$.

The cut-off is precisely what fails at reachable sizes. At ten million, primes up to the square root are those below 3,163, and the sum of $1/p$ over those is about 2.35, against about 3.04 for all primes up to ten million: nearly a quarter of the expected count comes from primes too large to behave independently. In the limit that share shrinks, since $\log \log N^{1/2}$ and $\log \log N$ differ by $\log 2$, a fixed amount; at reachable sizes it is nearly a quarter of everything.

Independence of this kind — chances multiplying across different primes, true for small primes and only approximately for large ones — is also the heuristic behind the patterns primes are allowed to make, where it predicts how often twin primes and other patterns occur. The same approximate independence underlies the sieve that cannot finish, which asks how many numbers survive after removing the multiples of many primes, and two halves a sieve cannot tell apart, where the parity of the number of prime factors — whether $\Omega(n)$ is even or odd — is exactly the quantity that the independence heuristic cannot see.

One large prime, usually #

The failure of independence has a vivid form. Among the million numbers from nine million to ten million, 72.7% have a prime factor larger than their own square root — and a number can have at most one such factor, since two of them would multiply to more than the number. As the numbers grow, that share falls towards $\log 2 \approx 69.3\%$, a limit that follows from Dickman’s work on the sizes of prime factors in the 1930s. So most numbers consist of one large prime and a small remainder, and the small remainder is where nearly all of the variation in the count of prime factors lives.

That picture explains both figures at once. The average count is right because it adds up the chances $1/p$ over all primes, and the one large prime contributes its share of that sum whichever prime it happens to be. The variance is too small because the large primes are mutually exclusive rather than independent: a number has one of them or none, never several, and a sum of mutually exclusive events varies far less than a sum of independent ones with the same chances. The independent model treats the primes between the square root and the number as a few hundred thousand separate coins; the numbers themselves treat them as a single coin with many faces.

In the limit the large primes become a negligible share of the count, because the count grows without bound while their contribution, about $\log 2$ on average, stays fixed. At reachable sizes a fixed contribution of 0.7 out of a total of 3 is not negligible at all, and it is precisely the part of the count that refuses to behave like a sum of independent pieces.

What the counts do not show #

The figures count every number up to ten million, so within that range they are complete, and the comparisons with formulas are exact up to rounding. What they cannot show is the behaviour of the error terms beyond ten million, except through the slow trends they display: the variance creeping towards $\log \log N$ and the standardised curves barely moving over a thousandfold range. Extrapolating those trends is guesswork, and the guesswork is the reason the theorems were needed.

The figures also concern the count of prime factors of a random number, which is a different question from the factors of special numbers — the class numbers drawn at random, whose divisibility by small primes follows a different and stranger law, or the numbers of the form $2^p - 1$, whose prime factors are constrained by their form.

Still open: the error, exactly #

The Erdős–Kac theorem has been sharpened in several directions — the rate of convergence, the probabilities of large deviations, the joint distribution of the counts of prime factors in different ranges — and its general shape is settled. What remains open are versions that apply to sparse sets of numbers: the count of prime factors of $n^2 + 1$, of the numbers one less than a prime, of the values of a polynomial at whole numbers. For many such sets the analogue of Erdős–Kac is known; for others, proving it would require knowing that the set contains the expected number of numbers with few prime factors, which runs into the same barriers as the problem of twin primes.

And the second-order behaviour visible in the figures is worked out only in part. The variance of $\omega(n)$ up to $N$ is $\log \log N$ plus a constant plus terms that decrease like powers of $1/\log \log N$ and $1/\log N$, all of which can be expanded; the figures show the variance trailing by about 1.7, which includes those decreasing terms at full strength. A version of Erdős–Kac with corrections precise enough to predict the histogram at ten million — the Sathe–Selberg formula is the closest — still has error terms comparable to the effect when $\log \log N$ is three.