Prime list
Prime numbers list for any range
Pick a start and an end, up to 100 trillion and 10 million numbers wide. The sieve finds every prime in between.
25 primes from 1 to 100
- First · last
- 2 · 97
- Twin-prime pairs
- 8
- Largest gap
- 8 (89 → 97)
- x / ln x estimate
- ≈ 22
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
How the sieve of Eratosthenes works
Around 240 BC Eratosthenes of Cyrene described a way to find primes without dividing anything. Write the numbers out, then cross out every multiple of 2 after 2, every multiple of 3 after 3, and so on with each number that is still standing. Whatever survives is prime. For ranges of up to 400 numbers the grid above shows the result, each composite struck through in the colour of the prime that removed it.
You only need to sieve with the primes up to √(end), because a composite number no larger than N always has a factor no larger than √N. That is why the grid for 1 to 100 is finished once the multiples of 7 are gone.
For large ranges the calculator runs a segmented sieve. It finds the primes up to √(end) once, then sieves your range in slices of about half a million odd numbers, so memory stays small even near 1014. Big jobs run in a background worker with a progress bar.
Under the count you'll see Gauss's estimate x / ln x from the prime number theorem, the number of twin-prime pairs (primes 2 apart, such as 41 and 43) and the widest gap between neighbouring primes in the range.
Sources
- Sieve of Eratosthenes, including the segmented version; the method is credited to Eratosthenes in Nicomachus of Gerasa's Introduction to Arithmetic.
- OEIS A006880: the number of primes below 10n, used to test this page's counts.
- Euclid, Elements, Book IX, Proposition 20: there are more primes than any given number of them.
Questions
How many primes are there below a million?
78,498. Below ten million there are 664,579 and below a billion 50,847,534. Primes thin out slowly: around x, roughly one number in ln x is prime.
Why is a range limited to 10 million numbers?
A wider range means hundreds of thousands of primes on one page and a download of many megabytes. Split a big job into several ranges instead; each takes about a second.
Are there infinitely many primes?
Yes. Euclid's argument: multiply any finite list of primes together and add 1. The result leaves remainder 1 when divided by each prime on the list, so its prime factors must all be new.