Sieve of Eratosthenes: Prime Marking Pattern

Learning Outcome

After this lesson, you should be able to mark composites once from p squared and collect primes efficiently.

Problem Statement

Given n, return all prime numbers less than or equal to n.

Brute Force Approach

Run a separate prime check for every number from 2 to n. This repeats factor checks across many numbers.

Optimized Approach

Keep a boolean table. When p is still marked prime, mark p p, p p + p, and later multiples as composite.

Exact Pseudocode

if n < 2:
  return []
isPrime[0..n] = true
isPrime[0] = false
isPrime[1] = false
for p from 2 while p * p <= n:
  if isPrime[p]:
    for multiple from p * p to n step p:
      isPrime[multiple] = false
return all indexes still marked true
  

Reference Code

class Solution:
    def primesUpTo(self, n):
        if n < 2:
            return []

        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False

        p = 2
        while p * p <= n:
            if is_prime[p]:
                for multiple in range(p * p, n + 1, p):
                    is_prime[multiple] = False
            p += 1

        return [i for i in range(2, n + 1) if is_prime[i]]
  

Sample Dry Run

Complexity

Edge Cases

• n less than 2 should return an empty list.
• Start marking at p * p to avoid repeated work.
• Use a wide integer for p * p when n can be large.

Interview Checklist

• Initialize 0 and 1 as not prime.
• Only mark multiples when p is still prime.
• Collect indexes that remain true.

FAQs

Smaller multiples of p already have a smaller prime factor and were marked earlier.

Once p squared is greater than n, remaining unmarked numbers are prime.

Prime marking table.