Problem
Return all prime numbers from 2 through limit. A prime is an integer greater than 1 divisible only by 1 and itself. Use the sieve idea: keep the next unmarked number and mark its larger multiples as composite. List results in ascending order.
Implement sieve_primes(limit).
Input
limit: The largest number that may be included.
Output
Return the primes in ascending order, or an empty list if none exist.
Constraints
0 ≤ limit ≤ 100,000. The upper bound is inclusive. Output tests verify results, not the exact algorithm used.
Examples
Input:
limit = 12
Expected output:
expected = [2, 3, 5, 7, 11]Input:
long long limit = 12;
Expected output:
std::vector<long long> expected = {2, 3, 5, 7, 11};Input:
long limit = 12;
Expected output:
long[] expected = new long[] {2, 3, 5, 7, 11};Explanation
Mark multiples of 2 and 3 as composite. The remaining values up to 12 are 2, 3, 5, 7, and 11.
Input:
limit = 1
Expected output:
expected = []Input:
long long limit = 1;
Expected output:
std::vector<long long> expected = {};Input:
long limit = 1;
Expected output:
long[] expected = new long[] {};Explanation
Prime numbers begin at 2, beyond this limit.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Mark composites starting from each unmarked prime candidate and continue through the limit.
Hint 2
Only numbers that stay unmarked at the end are prime.
Hint 3
Stop marking multiples once the candidate’s square exceeds the limit.
Expected complexity
O(n log log n) time, O(n) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.