Prime Numbers Up to N (Sieve With Loops)

Hard ⏱ 18 min 32% acceptance ★★★★☆ 4.2

Write a function primes_up_to(n) that returns a sorted list of all prime numbers less than or equal to n, computed using the Sieve of Eratosthenes implemented with nested loops (a boolean list marking composites).

Examples

Example 1

Input

primes_up_to(20)

Output

[2, 3, 5, 7, 11, 13, 17, 19]

Explanation

All primes up to 20.

Example 2

Input

primes_up_to(1)

Output

[]

Explanation

No primes exist at or below 1.

Constraints

n is a non-negative integer.

Topics

Loopsnested loops

Companies

AmazonApple

Hints

Hint 1

Create a boolean list `is_prime` of size n+1, initialized True, with index 0 and 1 set False.

Hint 2

For each prime p found, mark all its multiples starting at p*p (or 2*p) as not prime using an inner loop.

← Pascal's Triangle Using Nested Loops Matrix Transpose Using Nested Loops →

Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.