Überprüfung, ob eine Zahl eine Primzahl ist – schnell
Bisher haben wir herausgefunden, ob eine Zahl
n prim ist oder nicht, indem wir im Wesentlichen eine lineare Suche nach Teilern durchgeführt haben. Das bedeutet, dass mit steigender Größe von n auch die Anzahl der Operationen, um festzustellen, ob n prim ist, proportional zunimmt (mit einem entsprechenden konstanten Faktor). In den ungünstigsten Fällen (wenn n tatsächlich eine Primzahl ist – etwa 51, 107 usw.) hat unser Algorithmus ungefähr n/4 Operationen benötigt, um die Primzahleigenschaft von n zu überprüfen.Wenn wir
n also verzehnfachen, führt dieser Algorithmus zehnmal so viele Operationen aus. Erhöhen wir n um den Faktor 100, würde der Algorithmus 100-mal mehr Operationen ausführen. Das heißt, unser Verfahren skaliert proportional zu n. Gibt es eine Möglichkeit, diesen Vorgang schneller zu gestalten? Es scheint, als würden wir noch immer viele unnötige Prüfungen durchführen.Der -Ansatz:
Stellen wir uns vor, die Zahl
n hat einen Teiler d.Das bedeutet, dass
n durch d teilbar ist und sowohl d als auch ganze Zahlen sind. Außerdem ist entweder d oder kleiner oder gleich . Wenn wir also prüfen, ob n prim ist, können wir statt bis lediglich bis iterieren. Wir wollen ja nur ausschließen, dass n durch irgendeine andere Zahl außer 1 oder n selbst teilbar ist. Daher genügt es, den kleineren der beiden möglichen Teiler d oder zu prüfen. Da einer der beiden kleiner als ist, können wir unsere Schleife bei beenden.Das ist eine enorme Verbesserung! Statt
n Operationen nur Operationen durchzuführen, macht einen großen Unterschied. Stellen wir uns ein Programm vor, das 10 Jahre (3650 Tage) benötigen würde, um eine Berechnung abzuschließen. Optimiert man es so, dass es statt n nun Operationen ausführt, würde es nur noch 2 Monate (61 Tage) dauern.Gibt es noch bessere Algorithmen, um die Primzahleigenschaft zu prüfen?
Ja! Mehr Informationen dazu findest du unter Algorithms for Competitive Programming. Es gibt Verfahren, deren Laufzeit mit zunehmendem
n nur logarithmisch wächst statt in der Größenordnung von .Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Ausgabe
Das Programm soll
Yes ausgeben, falls n eine Primzahl ist, und andernfalls No.Beispiele
Input | Output |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB