Prime Sieve Generator

Build a lazy generator that yields prime numbers up to a given limit.

generators prime sieve

Write a generator function `prime_gen(limit)` that yields all prime numbers less than or equal to `limit` in ascending order. Use an efficient algorithm such as the Sieve of Eratosthenes. Do not return a list; the function must be a generator (using `yield`). If `limit` is less than 2, the generator should yield nothing.

Constraints

The input `limit` is an integer with 0 <= limit <= 10^7. The expected complexity is O(n log log n) time and O(n) space.

Example

>>> list(prime_gen(10))
[2, 3, 5, 7]
>>> list(prime_gen(1))
[]
>>> list(prime_gen(20))
[2, 3, 5, 7, 11, 13, 17, 19]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a boolean list `is_prime` where each index represents the primality of that number.

Start marking multiples from 2 upward; when you find a prime, yield it and mark its multiples as non-prime.

You can optimize by only checking multiples starting from i*i for each prime i.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.