1. Assume all prime
Start by assuming every number is prime, then cross out composites.
const isPrime = new Array(n + 1).fill(true)Typorithm · medium
Sieve of Eratosthenes
▷ Interactive algorithm labsieve-of-eratosthenesmathprimesmarkingmultiples
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Sieve of Eratosthenes
Math & Number Theory
Mark every number prime, then cross out multiples of each prime starting at its square.
Instead of testing each number, the sieve eliminates composites in bulk.
For each prime i, all multiples from i*i upward are crossed out — smaller ones already are.
Sieving only up to sqrt(n) suffices, since any composite has a factor at most sqrt(n).
Preparing algorithm lab…
01
Start crossing out at i*i.
02
Sieve i only up to sqrt(n).
03
Survivors are prime.
function sieve(n) {
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = false;
isPrime[1] = false;
for (let i = 2; i * i <= n; i += 1) {
if (isPrime[i]) {
for (let j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
const primes = [];
for (let i = 2; i <= n; i += 1) {
if (isPrime[i]) primes.push(i);
}
return primes;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Up to sqrt(n)
Only sieve from primes up to sqrt(n); larger ones are already marked.
for (let i = 2; i * i <= n; i += 1)3. Start at i squared
Smaller multiples of i were already crossed out by smaller primes.
for (let j = i * i; j <= n; j += i)4. Cross out
Mark each multiple of i as composite.
isPrime[j] = false5. Collect primes
Whatever stays true is prime.
if (isPrime[i]) primes.push(i)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.