It shouldn’t have been too hard, based on what he knew. Let us take a look.

Euler knew that the sum of reciprocal primes diverged, and he even knew the growth rate of , where the sum is taken only over primes . His method of discovering this was rather elegant, even if his lack of respect for divergent series may look horrifying to a modern mathematician. It was already known earlier that the harmonic series grows like ; that is,

,

or more precisely,

.

Euler had earlier worked out the famous Euler product for the zeta function:

for . (This formula has a delightful interpretation as an analytic formulation of the fundamental theorem of arithmetic.) Since neither side of the above formula makes sense when , Euler did the most logical thing possible and set anyway, to obtain

.

Taking logarithms, he then obtained

,

and expanding out all the logarithmic terms on the right as power series and regrouping, the right side becomes

.

Since all the terms except the first add up to something finite, they will not make a significant contribution in the limit, so Euler ignored them. (He could also have truncated after the first term when expanding the logarithms as power series, which would have had the same effect.) Hence, in the limit,

.

Naturally, that should be interpreted as

.

One can get rid of all the divergent series and weird expressions like by taking limits and being careful with error terms like a modern mathematician would do. But that wasn’t a necessary part of the culture in the 18^{th} century.

At this point, Euler stopped, but I don’t understand why. It is now possible to make an estimate for the number of primes up to , using a quick and easy computation. Since I’m a rebellious mathematician, I did the following computation on the *front* of an envelope.

Let us try to estimate the number of primes between and , for some , and let us write for the number of primes up to . Then

,

where the explanation for the last term is that, if is not much bigger than 1, then each summand on the left is roughly . The goal is now to determine . We have

.

Expanding the logarithm using a power series and truncating after the first term, we obtain

.

Now, choosing and again taking the first term of the power series for the logarithm (that seems to be the name of the game today), we obtain

.

Now, summing over gives

(where I wrote 2 instead of 1 as the lower bound for the sum and integral to make them converge). And that’s one version of the prime number theorem. Nothing here would have caused Euler to break a sweat. But yet Gauss seems to have been the first one to conjecture the prime number theorem, and even he apparently did so on the basis of actually working out tables of primes and counting.