Prime Number Project

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. This means it cannot be divided evenly by any number other than 1 and itself.

Examples of Prime Numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...

These primes less than 100 were known as early as 1202. There are 78498 prime numbers less than one million (7.85%) which can be computed very rapidly on modern computers. It wasn't until 1785 that these primes were first computed.

The number of primes less than or equal to a value is a foundational function in number theory known as the Prime Counting Function \(π(n)\). Computing \(π(n)\) for large values of \(n\) is often used to test new super computers.

**Number of Primes Computed**
(Source: Wolfram MathWorld)
\(n\)	\(π(n)\)	Source
10¹	4	antiquity
10²	25	L. Pisano (1202; Beiler)
10³	168	F. van Schooten (1657; Beiler)
10⁴	1229	F. van Schooten (1657; Beiler)
10⁵	9592	T. Brancker (1668; Beiler)
10⁶	78498	A. Felkel (1785; Beiler)
10⁷	664579	J. P. Kulik (1867; Beiler)
10⁸	5761455	Meissel (1871; corrected)
10⁹	50847534	Meissel (1886; corrected)
10¹⁰	455052511	Lehmer (1959; corrected)
10¹¹	4118054813	Bohmann (1972; corrected)
10¹²	37607912018
10¹³	346065536839
10¹⁴	3204941750802	Lagarias et al. (1985)
10¹⁵	29844570422669	Lagarias et al. (1985)
10¹⁶	279238341033925	Lagarias et al. (1985)
10¹⁷	2623557157654233	M. Deleglise and J. Rivat (1994)
10¹⁸	24739954287740860	Deleglise and Rivat (1996)
10¹⁹	234057667276344607	M. Deleglise (June 19, 1996)
10²⁰	2220819602560918840	M. Deleglise (June 19, 1996)
10²¹	21127269486018731928	pi(x) project (Dec. 2000)
10²²	201467286689315906290	P. Demichel and X. Gourdon (Feb. 2001)
10²³	1925320391606803968923	T. Oliveira e Silva (pers. comm., Apr. 7, 2008)
10²⁴	18435599767349200867866	Platt
10²⁵	176846309399143769411680	Büthe (2014)
10²⁶	1699246750872437141327603	Staple (2015)
10²⁷	16352460426841680446427399	D. Baugh and K. Walisch (2015)

The Prime Counting Function is a step-wise function as the value only changes once we reach a new prime. As primes are not distributed evenly (the become more sparse as \(n\) gets larger) we see the graph of \(π(n)\) flatten out gradually. It never approaches a limiting value as there are an infinite number of primes (Euclid’s theorem).

Prime Counting Function Graph — Prime Counting Function computed with prime_counting_graph.py

C++ program to compute \(π(n)\)

If we divide the Prime Counting Function by \(n\) we get an approximation for the density of primes at \(n\). This graphic of the density of primes gets smaller and smaller but never reaches zero. It does, however, have a lower bounding function of \(\frac{1}{\ln(n)}\).

Prime Density Function Graph — Prime Density Function computed with prime_density_graph.py

Binary Files

These files contain all the primes between 2 to the specified value that I have computed. They can be quite large, so they have been compressed using gzip. I had to make the file extensions .gzip so that the web server wouldn't automatically decompress the files after downloading. You will need to change the extension on the files to .gz and decompress them with the command

gunzip -k <filename.gz>

Be advised that the files get about 10x larger when decompressed.

Primes 2 - 10⁹ (50,847,534 primes, 74MiB)
Primes 2 - 10¹⁰ (455,052,511 primes, 670MiB)
Primes 2 - 10¹¹ (4,118,054,813 primes, 6GiB)
Primes 2 - 10¹² (37,607,912,018 primes, 55GiB)

The files are in binary format. They consist of a sequence of 64-bit integer values in little-endian format. You can use the following C++ programs to convert between binary and text formats.

Convert binary to text program

Convert text to binary program

References

Computing Prime Numbers

Computed with a Raspberry Pi 5 Cluster