Skip to content
Hello Python

Generate Primes with a Sieve

Practice ExerciseIntermediateMediumArraySieve of Eratosthenes

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement primes_up_to(limit). Return every prime less than or equal to limit in ascending order by marking composite multiples with a Sieve of Eratosthenes.

Starter code

def primes_up_to(limit):
    pass
Test cases

through-thirty

{
  "args": [
    30
  ]
}

Expected: [2,3,5,7,11,13,17,19,23,29]

below-two

{
  "args": [
    1
  ]
}

Expected: []

Wizard outline
  1. Step 1: Handle limits below the first prime

    Return an empty result when limit is less than 2. Two is the smallest prime, so no candidate exists below it.

  2. Step 2: Build flags and mark multiples of two

    Represent candidates explicitly and eliminate even composites. A boolean table lets each composite be crossed out without repeated divisibility tests.

  3. Step 3: Cross out every composite family

    Advance candidates through the square-root boundary. Every composite has a prime factor no larger than its square root.

Footguns and prerequisites
  • Leaving 0 and 1 marked produces false primes.
  • Starting at 2p repeats work already performed by smaller primes.
  • functions
  • lists and tuples
  • control flow
Reviewed references
Recommended approach and implementation

Mark all candidates, cross out multiples from p squared for each remaining prime p, then collect marked values.

Why it works: Every composite has a prime factor no greater than its square root and is crossed out. No prime is a multiple of a smaller prime, so marked values are exactly the primes.

def primes_up_to(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [value for value in range(2, limit + 1) if is_prime[value]]