Sieve of Eratosthenes
List primes by crossing out multiples.
Key idea
List primes by crossing out multiples.
In depth
List the numbers, then repeatedly cross out multiples of each prime, starting at its square. What remains is prime. Only primes up to √n need to be used.
Worked example
Primes up to 30: cross out multiples of 2, 3, 5 to leave 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Real-world uses
- Generating lists of primes quickly for testing and cryptographic key generation
Common mistake
Crossing out the prime itself.
How to learn this
- Read the key idea and say it in your own words.
- Work through the worked example, then try a similar problem.
- Use the interactive lesson’s visual and mini-quiz to check the pattern.
Frequently asked questions
What is Sieve of Eratosthenes?
List primes by crossing out multiples. It is a topic at the intermediate level in Discrete Math & Number Theory.
Where is Sieve of Eratosthenes used in real life?
Real-world examples: Generating lists of primes quickly for testing and cryptographic key generation.
What should I learn before Sieve of Eratosthenes?
Make sure you are comfortable with Infinitude of Primes, the previous topic in Discrete Math & Number Theory.
What is a common mistake with Sieve of Eratosthenes?
Crossing out the prime itself.
How can I practise Sieve of Eratosthenes?
Open the interactive lesson, play with the visual, then answer the three-question mini-quiz. Getting two right marks the topic complete.
What comes after Sieve of Eratosthenes?
Move on to Prime Number Theorem next.
Related intermediate topics in Discrete Math & Number Theory
- Statements and Truth Values – A proposition is true or false, never both.
- Logical Connectives – AND, OR, NOT, implication and biconditional.
- Truth Tables – List all truth assignments to evaluate compound statements.
- Subsets and Power Sets – A set with n elements has 2ⁿ subsets.
- Set Operations – Union, intersection, difference and complement.
- Venn Diagrams – Pictures of sets and their overlaps.