Try the prime checker first. The sieve is best when you want many primes up to a limit. If you only want to test one number, use the Prime Number Checker. That gives the fastest path for a single yes-or-no question, while the sieve explains how a whole set of primes is built.
Open Prime Number CheckerQuick answer: The Sieve of Eratosthenes is a method for finding every prime number up to a chosen limit. It works by listing the integers, then crossing out multiples of each prime you meet. The numbers left behind are prime.
This method is still taught because it shows a clean truth about primes: composite numbers reveal themselves through their factors. Instead of checking each number one by one with repeated division, the sieve removes whole groups of non-primes in an orderly way.
What the Sieve of Eratosthenes is
The Sieve of Eratosthenes is not a formula that magically spits out primes. It is a filtering process. You start with the integers from 2 up to some limit n. Then you remove numbers that cannot be prime because they are multiples of smaller primes.
A prime number has exactly two positive divisors: 1 and itself. A composite number has more than two. The sieve uses that fact directly. Once you know that 2 is prime, every larger multiple of 2 is composite. Once you know that 3 is prime, every larger multiple of 3 is composite. The pattern keeps going.
This idea is linked to several nearby topics in prime number study:
- prime testing, where you ask whether one number is prime
- prime generation, where you want all primes in a range
- factorization, where composite numbers are broken into prime factors
- divisibility, which explains why multiples can be removed with confidence
Why the sieve works
The logic is simple, but it is worth stating clearly. Every composite number has at least one prime factor. That means a composite number cannot hide forever. It must show up as a multiple of some smaller prime.
Core idea: if a number m is composite, then m = a × b for integers larger than 1. At least one of those factors is prime, or contains a prime factor. So m will be crossed out when the sieve marks multiples of that prime.
This is why the method feels so elegant. You do not need a separate proof for each number. The structure of composite numbers does the work for you.
What stays
Numbers never crossed out are prime.
What goes
Multiples of known primes are composite.
Why it is efficient
You remove many non-primes at once instead of testing one number at a time.
Step-by-step example up to 30
A small example makes the method feel natural. Start with the integers from 2 to 30:
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
Step 1: Start with 2
2 is prime, so cross out every multiple of 2 larger than 2:
4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
Step 2: Move to the next number not crossed out
The next number still standing is 3. So 3 is prime. Cross out every multiple of 3 larger than 3:
6, 9, 12, 15, 18, 21, 24, 27, 30
Some of these were already removed by 2. That is normal.
Step 3: Continue with 5
The next number not crossed out is 5. Cross out its multiples:
10, 15, 20, 25, 30
Step 4: Continue with 7
The next number not crossed out is 7. Cross out:
14, 21, 28
What remains
The numbers left are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
These are all the prime numbers up to 30.
Why you start crossing out at p²
This is one of the most useful details, and many short articles skip it.
Suppose you are working with a prime p. You do not need to start at 2p. In practice, you start at p².
Why? Because smaller multiples of p were already handled earlier.
2pwas removed when you processed 23pwas removed when you processed 34pwas removed when you processed 2 again, since 4 is not prime- and so on
So when you reach prime p, the first new multiple worth crossing out is usually p². This small idea cuts repeated work and makes the sieve much cleaner.
Why you only need to go up to √n
Another detail that matters: you do not need to process every number up to n. You only need to keep sieving while the current prime p satisfies p² ≤ n.
Here is the reason. If a composite number is at most n, then it must have a factor at most √n. If both factors were larger than √n, their product would be larger than n.
Practical stopping point: once you pass √n, every composite up to n has already been marked by a smaller factor.
This is a big part of why the sieve is faster than naive checking for every number in the list.
What makes the sieve faster than repeated prime checks
If your goal is to test one number, trial division or a prime checker is often the easier choice. But if your goal is to list all primes up to a limit, the sieve wins because it reuses information.
Instead of asking, “Is 97 prime? Is 98 prime? Is 99 prime?” as separate tasks, the sieve treats the whole interval as one structure. Once you know 2 is prime, that fact helps with many numbers. The same happens with 3, 5, 7, and the rest.
That reuse is the real strength of the algorithm.
| Task | Better choice | Why |
|---|---|---|
| Test one number | Prime Number Checker | Simple yes-or-no result without generating a full list |
| List all primes up to n | Sieve of Eratosthenes | Marks many composites in batches |
| Study prime patterns in a range | Sieve of Eratosthenes | Gives the full prime set, not just one answer |
| Understand why composites fail | Sieve of Eratosthenes | Shows multiples and factors in a visible way |
Time and memory behavior
The classic sieve runs in about O(n log log n) time and uses O(n) memory for the marking array. You do not need that notation to use the idea, but it helps explain why the algorithm appears so often in math and programming.
In plain language:
- it is fast for generating primes up to a limit
- it becomes memory-heavy when the limit gets very large
- that is why larger versions such as the segmented sieve are used in programming work
The classic method is still the right place to learn. It gives the mental model that later versions build on.
Common mistakes when learning the sieve
Crossing out the prime itself
When you process 2, you keep 2. You only remove larger multiples of 2. The same rule holds for every prime.
Starting at 2p instead of p²
This still works, but it repeats work. Starting at p² is cleaner and more efficient.
Thinking the sieve proves primality by division
It does not test each candidate in isolation. It eliminates composite numbers through the structure of multiples.
Using the sieve for the wrong task
If you only care about one number, a checker is usually the better fit. The sieve shines when the target is a whole range.
A useful distinction: a prime checker answers, “Is this number prime?” A sieve answers, “Which numbers up to this limit are prime?” They are related, but they solve different jobs.
Where this method fits in the prime number ecosystem
On a site focused only on prime numbers, the sieve matters because it connects several ideas that otherwise feel separate.
- Prime lists: it gives the actual sequence of primes up to a bound
- Prime gaps: once you have the list, you can measure differences between neighboring primes
- Twin primes: the sieve makes pairs like 11 and 13 easy to spot
- Prime density: it gives a concrete way to see how primes thin out as numbers grow
- Factorization basics: crossed-out numbers hint at their smaller prime factors
This is one reason the Sieve of Eratosthenes remains so valuable. It is not just a trick for a classroom page. It sits near the center of how many prime-number ideas connect.
A short historical note
The method is named after Eratosthenes, a Greek mathematician and scholar from the 3rd century BCE. The idea has lasted because it is direct, visual, and mathematically honest. It does not hide the logic behind a black box. You can watch non-primes disappear and primes remain.
That clarity is why the sieve still appears in modern math education and programming.
Why the sieve still matters today
Modern systems do not use the basic classroom version for every large prime task. But the idea still matters. Small-prime filtering, segmented sieves, and many teaching tools all rest on the same insight: multiples expose composite numbers very efficiently.
For readers on a prime number site, this is the practical takeaway:
- use a checker when you want one result
- use a sieve when you want a prime list
- learn the sieve if you want to understand why prime generation works
FAQ
Is the Sieve of Eratosthenes only for small numbers?
No. The classic version is excellent for moderate limits and for learning. For very large limits, programmers often use a segmented version because it saves memory.
Why does the sieve start at 2 instead of 1?
Because 1 is not prime. A prime number must have exactly two positive divisors, and 1 has only one.
Can the sieve tell me whether one number is prime?
It can, but that is not its most natural job. The sieve is built for generating all primes up to a limit. For a single number, a dedicated Prime Number Checker is usually more direct.
Why do we stop at the square root of the limit?
Because every composite number up to the limit has a factor at or below that square root. After that point, any remaining unmarked numbers are prime.
Is the Sieve of Eratosthenes the same as prime factorization?
No. The sieve removes composite numbers from a range. Prime factorization breaks one number into prime pieces. The two ideas are related through divisibility, but they are not the same process.
If you are exploring prime numbers one value at a time, check the number directly. If you are exploring a whole interval, the sieve gives the clearer picture.