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.
Einschränkungen
0 ≤ limit ≤ 100,000. The upper bound is inclusive. Output tests verify results, not the exact algorithm used.
Beispiele
Eingabe:
limit = 12
Erwartete Ausgabe:
expected = [2, 3, 5, 7, 11]Eingabe:
long long limit = 12;
Erwartete Ausgabe:
std::vector<long long> expected = {2, 3, 5, 7, 11};Eingabe:
long limit = 12;
Erwartete Ausgabe:
long[] expected = new long[] {2, 3, 5, 7, 11};Erläuterung
Mark multiples of 2 and 3 as composite. The remaining values up to 12 are 2, 3, 5, 7, and 11.
Eingabe:
limit = 1
Erwartete Ausgabe:
expected = []Eingabe:
long long limit = 1;
Erwartete Ausgabe:
std::vector<long long> expected = {};Eingabe:
long limit = 1;
Erwartete Ausgabe:
long[] expected = new long[] {};Erläuterung
Prime numbers begin at 2, beyond this limit.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Mark composites starting from each unmarked prime candidate and continue through the limit.
Hinweis 2
Only numbers that stay unmarked at the end are prime.
Hinweis 3
Stop marking multiples once the candidate’s square exceeds the limit.
Erwartete Komplexität
O(n log log n) time, O(n) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.