Get started

Sieve of Eratosthenes Coding Problems: 1 Question with Solutions

1 sieve of eratosthenes coding problem — 1 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 1-day plan.

  • Problems: 1
  • By difficulty: 1 medium
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

The sieve of Eratosthenes finds every prime up to n in one pass: start with every number marked prime and, for each prime p, cross out its multiples from p² onwards; whatever survives is prime. It replaces n separate primality tests with crossing-out that costs O(n log log n), close to linear. The problems here practise the sieve and the variants built on the same loop, such as counting the primes below n or recording each number's smallest prime factor so any number up to n factorises in a few divisions.

How sieve of eratosthenes works, step by step

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495015 primes ≤ 5034 composites crossed out
All primes up to 50, with the sieve of Eratosthenes. Example: n = 50
  1. Write out 1 to 50 and treat every number from 2 up as possibly prime; 1 is neither prime nor composite. Instead of testing each number for divisors, the sieve crosses out the multiples of each prime it finds.
  2. 2 is not crossed out, so it is prime. Cross out its multiples from 2 × 2 = 4 in steps of 2: 24 new. Every even number above 2 has 2 as a factor, so none of them is prime.
  3. 3 is not crossed out, so it is prime. Cross out its multiples from 3 × 3 = 9 in steps of 3: 7 new, 7 already gone. Starting at 9 is safe: a smaller multiple k × 3 with k < 3 already fell to a prime factor of k, as 6 fell to 2.
  4. 5 is not crossed out, so it is prime. Cross out its multiples from 5 × 5 = 25 in steps of 5: 2 new, 4 already gone. Starting at 25 is safe: a smaller multiple k × 5 with k < 5 already fell to a prime factor of k, as 10 fell to 2.
  5. 7 is not crossed out, so it is prime. Cross out its multiples from 7 × 7 = 49 in steps of 7: 1 new. Starting at 49 is safe: a smaller multiple k × 7 with k < 7 already fell to a prime factor of k, as 14 fell to 2.
  6. The next uncrossed number is 11, and 11 × 11 = 121 > 50, so the sieve stops. Every composite up to 50 has a prime factor no bigger than √50 ≈ 7.1, so it has already been crossed out.
  7. The 15 numbers left uncrossed are the primes up to 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Each prime p crosses about n / p numbers, which adds up to O(n log log n) time, with O(n) memory for the marks.

Sieve of Eratosthenes study plan

The one Sieve of Eratosthenes problem (1 medium) over 1 day, about 50 min in all — the pattern first, then easiest to hardest. Then move on to Combinatorics.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Next topic: Combinatorics

Sieve of Eratosthenes: the essentials

When to reach for it

Primality or factors for many numbers below a bound you can allocate: count the primes below n, factorise every element of an array with values up to 10⁶. Trial division costs O(√n) a number, O(n√n) for all; one sieve answers them all. For a single number, or values up to 10¹², trial division is the tool — see Number Theory.

The pattern

Mark every number from 2 up as prime. For each still-marked p with p × p ≤ n, cross out p², p² + p, p² + 2p and so on; a smaller multiple k × p with k < p has a smaller prime factor and is already crossed out. Record the first prime to reach each number and the sieve also factorises: divide x by its smallest prime factor until 1 is left, O(log x) steps. A number is prime when it is its own smallest factor.

def smallest_prime_factors(n):      # spf[x] for x <= n; spf[x] == x means prime
    spf = list(range(n + 1))
    p = 2
    while p * p <= n:
        if spf[p] == p:             # nothing smaller divides p, so p is prime
            for m in range(p * p, n + 1, p):
                if spf[m] == m:     # first prime to reach m is its smallest
                    spf[m] = p
        p += 1
    return spf

Cost

O(n log log n) time — the crossings sum to n/2 + n/3 + n/5 + …, about n × ln ln n — and O(n) memory: ten million flags are 10 MB as bytes, about 80 MB as a Python list.

Common mistakes

  • Stopping the outer loop before √n: range(2, int(sqrt(n))) leaves 49 marked prime when n = 49. The bound is p × p ≤ n, inclusive.
  • Allocating n flags, then clearing is_prime[0] and is_prime[1], which fails when n is 0 or 1 — Count Primes allows both.
  • Crossing out the multiples of every p, not only the primes: still correct, but O(n log n).
  • Counting 0 and 1 as primes because they were never cleared.

Start with

All sieve of eratosthenes problems

Medium (1)

Companies that ask sieve of eratosthenes problems

  • Adobe 1 problem on sieve of eratosthenes
  • Amazon 1 problem on sieve of eratosthenes
  • Google 1 problem on sieve of eratosthenes
  • Microsoft 1 problem on sieve of eratosthenes

Next topic: Combinatorics