Prüfe, ob eine Zahl prim ist – etwas schneller
Angenommen, ein Programm zur Überprüfung von Primzahlen wird derzeit in der Produktion eines großen Unternehmens eingesetzt. Mit dem rasanten Wachstum der Firma und der steigenden Zahl von Nutzern wächst auch der Umfang der Anfragen an deinen Code. Man bittet dich, das Programm zu optimieren und etwas schneller zu machen, damit das Unternehmen die wachsende Nutzerlast bewältigen kann.
Deine bisherige Lösung sah wahrscheinlich so aus:
- Eine Schleife über alle Zahlen von 2 bis
n, um die Anzahl der Teiler zu zählen.
- Eine Schleife über alle Zahlen von 2 bis
n, die sofort abbricht, sobald ein Teiler gefunden wurde.
Es gibt jedoch ein paar kleinere Feinjustierungen, um das Verfahren zu beschleunigen:
Optimierung 1:
Anstatt alle Zahlen von 2 bis
n zu prüfen, kann man zunächst testen, ob n durch 2 teilbar ist. Ist das nicht der Fall, braucht man bei den weiteren Überprüfungen keine geraden Zahlen (4, 6, 8, 10, 12, usw.) mehr zu berücksichtigen.Optimierung 2:
Statt von 2 bis
n zu iterieren, kann man die Schleife bis n/2 laufen lassen. Da der kleinste mögliche Teiler 2 ist, wird man über n/2 hinaus keine neuen Teiler mehr finden.Diese beiden Optimierungen lassen sich kombinieren. Dann werden nur die ungeraden Zahlen bis
n/2 betrachtet, sodass es ungefähr n/4 Kandidaten gibt. Dadurch wird der gesamte Ablauf gegenüber einem schlichten linearen Check etwa viermal so effizient.Zwar wird das Programm dadurch etwas schneller, aber die Komplexität bleibt grundsätzlich eine lineare Teilersuche. Das bedeutet, dass mit steigendem
n auch die Anzahl der durchgeführten Operationen proportional zunimmt. Wir werden später besprechen, wie man diesen Check drastisch beschleunigt und vom linearen Verhältnis zu n wegkommt.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 No andernfalls.Beispiele
Input | Output |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB