Sieve of Eratosthenes
List all primes up to N in near-linear time.
Sieve of Eratosthenes is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Primes in Bulk
Sometimes you need every prime up to N, not just one check. The Sieve of Eratosthenes finds them all in one sweep. 🧹
The Big Idea
Start by assuming every number is prime. Then cross out the multiples of each prime you find, leaving only true primes behind.
Set Up the Flags
Create a boolean list where index i marks whether i is prime. This array is the canvas the sieve paints on.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseMarch Through Candidates
Walk i upward. The first time you reach a number still flagged True, it must be a fresh prime with no smaller factor.
Cross Out Multiples
For each prime i, mark 2i, 3i, 4i and so on as not prime. Those multiples clearly have i as a divisor.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseStart at i Squared
Begin crossing out at i*i, not 2i. Every smaller multiple was already removed by an earlier prime, so skip them.
Stop at the Root
You only need to sieve while i*i stays at or below N. Past the square root, every remaining True flag is already prime.
The Full Sieve
Combine the outer scan and inner crossing-out. After the loop, every index still flagged True is a confirmed prime.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseCollect the Primes
Read the finished flags into a list with a comprehension. Now you hold every prime up to N ready for fast queries.
primes = [i for i, p in enumerate(is_prime) if p]Why It Is Fast
The sieve runs in about O(n log log n) time, nearly linear. That is why it crushes repeated single-number testing.
Mind the Memory
The flag array uses memory proportional to N. For very large limits, watch your space budget before allocating.
Quick Check
Recall the small optimization in the inner loop.
Recap
You can now build a sieve to list all primes up to N in near-linear time, starting each prime at i*i and stopping at the root. ✅
Frequently asked questions
Is the “Sieve of Eratosthenes” lesson free?
Yes — the full text of “Sieve of Eratosthenes” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Sieve of Eratosthenes”?
List all primes up to N in near-linear time. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Sieve of Eratosthenes” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.