# How did Gauss determine the number of primes?

In Brian Conrey's article on Riemann's hypothesis, one reads in the very beginning:

On Christmas Eve 1849 Gauss wrote a letter to his former student Encke in which he described his thoughts about the number of primes π(x) less than or equal to x. Gauss had developed his ideas around 1792 when he was 15 or 16 years old. His conclusion was that up to a small error term π(x) was close to $$li(x)$$ the logarithmic integral

$$li(x) = \int_2^x \frac{dt}{log\ t}$$

The strikingly good approximation was computed over and over by Gauss at intervals up to 3 million, all computed by Gauss himself who could determine the number of primes in a chiliad (block of one thousand numbers) in 15 minutes.

Is it known how Gauss could do that: determine the number of primes in up to 3,000 chiliads, which must have taken him 750 hours. What was his trick? And were his numbers correct or just good estimates?

• 15 minutes = 900 seconds, implying he spends less than one second per number. Sieving strikes me as just a tad too slow to do that, but Gauss was really good with numbers so maybe he found a shortcut. There are a few obvious optimizations, such as skipping even numbers. Commented Mar 10 at 17:47

For what it's worth:

As Goldshtein writes, “Evidently Gauss considered the tabulation of primes as some sort of pastime and amused himself by compiling extensive tables on how the primes distribute themselves in various intervals of length 1000.” To do this, he was using larger and larger tables of primes or tables of prime decomposition.18

These included (see the letter in Footnote 15) Vega’s Tables (available to Gauss in 1796, and listing primes up to 400,031), then in 1811 a friend made Gauss a present of Chernau’s cribrum (an exerpt is on the right 19) reaching 1,020,000. Finally, the Burckhardt’s factorization tables (published in 3 parts in 1814–17 and organized similarily to the cribrum) allowed Gauss to investigate primes up to the limit of these tables: to 3,000,000.

Footnote 18: Usually these tables were compiled by other people. However, since he could find some errors in these tables, apparently he have been duplicating at least some calculations himself.

Footnote 15: This is discussed in his letter to Johann Franz Encke of 1849 (in a book form)...

Source

Just a comment: looks like the author of Cribrum Arithmeticum was L. Chernac, not Chernau.