Problem
Gib alle Primzahlen von 2 bis einschließlich limit zurück. Eine Primzahl ist eine ganze Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Verwende das Sieb-Prinzip: Behalte die nächste unmarkierte Zahl und markiere ihre größeren Vielfachen als zusammengesetzt. Gib die Ergebnisse in aufsteigender Reihenfolge aus.
Implementiere sieve_primes(limit).
Eingabe
limit: Die größte Zahl, die enthalten sein darf.
Ausgabe
Gib die Primzahlen in aufsteigender Reihenfolge zurück oder eine leere Liste, falls keine existieren.
Einschränkungen
0 ≤ limit ≤ 100.000. Die obere Grenze ist inklusive. Die Ausgabetests prüfen die Ergebnisse, nicht den genauen verwendeten Algorithmus.
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
Markiere die Vielfachen von 2 und 3 als zusammengesetzt. Die verbleibenden Werte bis 12 sind 2, 3, 5, 7 und 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
Primzahlen beginnen bei 2, darüber hinaus liegt dieser Grenzwert.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Markiere Vielfache ab jedem noch unmarkierten Primkandidaten und arbeite bis zum Limit weiter.
Hinweis 2
Nur Zahlen, die am Ende unmarkiert bleiben, sind prim.
Hinweis 3
Hör auf, Vielfache zu markieren, sobald das Quadrat des Kandidaten das Limit überschreitet.
Erwartete Komplexität
Zeit O(n log log n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.