List all primes up to n (Sieve of Eratosthenes)
Coding problemEasy-MediumAsked in: Accenture, Capgemini, TCS
Given an integer n, return every prime number from 2 up to and including n, in increasing order. If there are none, return an empty list.
The largest hidden tests use n = 1,000,000, so testing each number by dividing it by every smaller number is too slow.
Examples
Example 1
Input: n = 10
Output: [2,3,5,7]
Example 2
Input: n = 13
Output: [2,3,5,7,11,13]
n itself is included when it is prime.
Example 3
Input: n = 1
Output: []
Constraints
- n is between 0 and 1,000,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.