Sieve of Eratosthenes Generator (Free) – List Primes & Find the Nth Prime
Enter an upper bound to generate a list of primes with the Sieve of Eratosthenes, visualized step by step. Also look up the Nth prime (up to the 1,000,000th) — free, browser-based, no sign-up.
Sieve of Eratosthenes for 1–100 (Reference Table)
Green cells are prime numbers; the rest were eliminated by the sieve.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
1 is neither prime nor composite, so it is left uncolored.
What the sieve of Eratosthenes does
The sieve of Eratosthenes is the classical algorithm for finding prime numbers, named after the Greek scholar of the third century BC. The idea is startlingly simple: take each number in turn from two upwards, declare it prime if it has not already been crossed out, and then cross out all of its multiples. Strike out the multiples of two, then those of the surviving three, then those of five — repeat as far as the square root of your limit and every number still standing is prime.
Give this tool an upper limit and it generates the list of primes up to one million. It displays the striking-out process step by step, so you can follow with your own eyes which prime removed which numbers. It also works in reverse, answering "what is the Nth prime?" for positions as large as the millionth. Everything is computed in your browser, so nothing you enter is sent anywhere.
How to generate a list of primes
- Enter the upper limit N Specify a whole number from 2 to 1,000,000. Starting with something small such as 100 makes the mechanics of the sieve much easier to see.
- Check the count and the largest prime You get how many primes lie at or below N — written π(N) — and the largest of them.
- Follow the striking-out steps For smaller limits, each stage shows which prime was used and which numbers it removed.
- Look up the Nth prime Enter a position and the tool returns the prime occupying it.
Tips for getting more out of it
- The Sieve of Eratosthenes efficiently lists all primes up to N by crossing out the multiples of each prime it finds, starting from 2.
- Set the upper bound N to 400 or below to see exactly which prime eliminated which number, step by step.
- The Nth-prime lookup supports queries like "what is the 1,000,000th prime," useful for confirming the existence of very large primes.
- Everything runs locally in your browser — the generated prime list is never sent to a server.
Where this helps
Studying algorithms
The sieve is the textbook example of O(n log log n) complexity, and watching it run makes the idea stick.
Verifying your own implementation
Compare the output of a sieve you have written yourself against this to confirm it produces the correct sequence.
Observing how primes are distributed
Varying the limit and watching π(N) grow gives a feel for the prime number theorem and its rough N / log N behaviour.
Background reading on cryptography
Public-key schemes such as RSA rest on large primes, and this is a way in to grasping how densely primes occur.
Prime and sieve terms explained
- Prime number
- A natural number of two or more whose only positive divisors are one and itself. One is not counted as prime.
- Composite number
- A natural number of two or more that is not prime. These are the numbers the sieve strikes out.
- π(N)
- The function giving the count of primes at or below N, known as the prime-counting function.
- Striking out
- Marking the multiples of a prime to exclude them from the candidates. The operation gives the algorithm its name.
- Why the square root suffices
- Any multiple of a prime larger than the square root of N has already been struck out as a multiple of some smaller prime.
- Prime number theorem
- The result that π(N) is asymptotic to N / log N, describing how quickly primes thin out.
FAQ
Side Note — Why a 2,000-year-old algorithm is still in use
The Sieve of Eratosthenes is one of the oldest surviving prime-generating algorithms, credited to the ancient Greek scholar Eratosthenes, who served as chief librarian of the Library of Alexandria in the 3rd century BCE. That a method devised over two millennia ago is still taught in computer science courses today speaks to its elegant simplicity.
The mechanism is disarmingly simple: list the integers starting from 2, treat the smallest unmarked number as prime, and cross out all of its multiples. Repeat this up to √N, and every prime up to N is revealed. For generating a full list of primes, this is far more efficient than testing each number individually with trial division.
The search for enormous primes continues today — distributed-computing projects like GIMPS (the Great Internet Mersenne Prime Search) keep discovering Mersenne primes with tens of millions of digits. The sieve itself is not used to find primes that large, but its core idea — mechanically eliminating multiples — underlies more advanced primality-testing algorithms.