sieveOfEratosthenes

Hard · Number Theory · 2 test cases

Implement the Sieve of Eratosthenes algorithm to find all prime numbers up to a given integer.

Examples

sieveOfEratosthenes(10) → [2, 3, 5, 7]
sieveOfEratosthenes(20) → [2, 3, 5, 7, 11, 13, 17, 19]

Starter code

function sieveOfEratosthenes(n) {

}

Complexity of the optimal solution

Time O(n log log n), space O(n). The Sieve of Eratosthenes is a highly efficient algorithm for finding all primes up to n. The time complexity is nearly linear. The space complexity is O(n) for the boolean array used to mark numbers.

Solve sieveOfEratosthenes in the browser