Ich habe diese Frage in einem Interview bekommen
Bitte geben Sie eine Lösung an, um zu überprüfen, ob eine Zahl eine Primzahl ist, indem Sie eine Schleife von eins - O (1) verwenden. Die Eingangsnummer kann nur zwischen 1 und 10.000 liegen.
Ich sagte, dass es unmöglich ist, wenn Sie nicht alle Primzahlen bis zu 10.000 gespeichert haben. Jetzt bin ich mir nicht ganz sicher, ob meine Antwort richtig war. Ich habe versucht, im Internet nach einer Antwort zu suchen, und am besten habe ich mir einen AKS-Algorithmus mit einer Laufzeit von O ((log n) ^ 6) ausgedacht.
Dies ist mit SoE (Sieb of Eratosthenes) möglich . Das Ergebnis ist ein Array von bools, das normalerweise als Einzelbit im BYTE/WORD/DWORDArray für eine bessere Speicherdichte codiert wird . Außerdem werden normalerweise nur die ungeraden Zahlen gespeichert, da die geraden außer 2 keine Primzahlen sind. Normalerweise bedeutet wahrer Wert, dass es keine Primzahl ist ....
Der naive O(1) C ++ - Code zum Überprüfen xwürde also so aussehen:
bool SoE[10001]; // precomputed sieve array
int x = 27; // any x <0,10000>
bool x_is_prime = !SoE[x];
Wenn das SoE als 8-Bit- BYTEArray codiert ist, müssen Sie den Zugriff ein wenig optimieren:
BYTE SoE[1251]; // precomputed sieve array ceil(10001/8)
int x = 27; // any x <0,10000>
BYTE x_is_prime = SoE[x>>3]^(1<<(x&7));
von grobem Konstruieren SoE ist nicht O(1)!!! Hier ein Beispiel, das es stark nutzt, um meine Minenfunktion zu beschleunigen IsPrime:
Dieser Artikel stammt aus dem Internet. Bitte geben Sie beim Nachdruck die Quelle an.
Bei Verstößen wenden Sie sich bitte [email protected] Löschen.
Lass mich ein paar Worte sagen