Herausforderung
In dieser Aufgabe erhalten Sie eine Ganzzahl N, für die Sie die der Ganzzahl nächstgelegene Primzahl ausgeben müssen.
Wenn die Zahl selbst eine Primzahl ist, geben Sie die Zahl aus.
Der Eingang N wird in einer einzelnen Zeile angegeben, die Eingänge werden durch EOF abgeschlossen. Die Anzahl der Eingänge würde 10000 Werte nicht überschreiten.
Die Herausforderung besteht darin, die schnellste Lösung zu implementieren, damit maximal 10000 Werte so schnell wie möglich verarbeitet werden können.
Eingang
299246598
211571591
71266182
645367642
924278231
Ausgabe
299246587
211571573
71266183
645367673
924278233
Einschränkungen
- N ist kleiner als 2 ^ 64
- Achten Sie auf Ihre Finger. Verwenden Sie nicht mehr als 4096 Byte in Ihrer Lösung.
- Sie können jede Sprache Ihrer Wahl verwenden, solange Sie keine eingebauten Dinge für die Primzahlen verwenden.
- Die schnellste Lösung mit der effizientesten Zeitkomplexität gewinnt!
HINZUGEFÜGT:
Dies ist eine einfachere Version desselben Problems (mit N <2 ^ 31), sodass Sie versuchen können, Ihren Ansatz in kleineren Fällen zu überprüfen, bevor Sie ihn für dieses eigentliche Problem erstellen.
code-challenge
primes
fastest-algorithm
Quixotic
quelle
quelle
Antworten:
Python
quelle
PARI GP
quelle
NextPrime[n]
funktioniert streng übern
3 Bedingungen ....Haskell
Sollte ziemlich schnell sein. Benötigt das Paket
primes
, verfügbar von Hackage.quelle
Rubin
quelle
Java
Dies dauert <1 Sekunde, bis num größer als 10 ^ 8 wird. Nicht effizient genug, wenn man bedenkt, dass 2 ^ 64 ungefähr 1,8 * 10 ^ 19 ist. (Begonnen vor 10 ^ 15 6 Minuten und läuft immer noch D :)
Dies gibt jedes Mal eine todsichere Antwort, da kein probabilistischer Algorithmus verwendet wird, dies jedoch in Bezug auf die Effizienz stark bezahlt wird - 10 ^ 18 hätte mehr als 5 Millionen Primzahlen in der Liste und noch mehr vor dem Sieben. Kann dies irgendwann mit einem besseren Siebalgorithmus verbessern. Ich erwarte nicht, dass dies einen der anderen schlägt :)
quelle
Haskell
Dies ist ziemlich schnell und bis zu einer großen Grenze nicht deterministisch. Auch mein allererster Haskell :).
wc
sagt 903b unkompiliert.Bearbeiten: Wenn jemand die zeitliche Komplexität abschätzen möchte, sei mein Gast ...
quelle