Check Prime Number

Q: Wie hoch ist die Zeitkomplexität für die Prüfung, ob eine Zahl eine Primzahl ist?

Die Probedivision bis √n benötigt O(√n) Zeit und O(1) Speicherplatz. Für n bis zu 2^31-1 sind das höchstens etwa 46,000 Divisionen oder 23,000 , wenn gerade Teiler übersprungen werden. Jeden Teiler bis n-1 zu testen, ist O(n) und erfordert für die größte Eingabe etwa zwei Milliarden Schritte.

Q: Warum prüfst du nur Teiler bis zur Quadratwurzel von n?

Teiler treten paarweise als d und n / d auf, deren Produkt n ist. Wären beide größer als √n , wäre ihr Produkt größer als n . Daher hat jedes Paar ein Element, das höchstens √n ist, und wenn bis dahin kein Teiler auftritt, ist n eine Primzahl.

Q: Ist 1 eine Primzahl?

Nein. Eine Primzahl hat genau zwei verschiedene Teiler, 1 und sich selbst, und 1 hat nur einen. Wenn man 1 auslässt, bleibt die Primfaktorzerlegung jeder ganzen Zahl eindeutig. Deshalb gibt isPrime(1) false zurück.

EinsteigerMathe und Simulation

+10

Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind. Du erhältst eine positive ganze Zahl n. Gib true zurück, wenn n eine Primzahl ist, andernfalls false. Die Zahl 1 ist keine Primzahl.

Funktion

isPrime(n: integer) → boolean

ninteger: die zu testende positive ganze Zahl
Gibt zurückboolean: true, wenn n eine Primzahl ist, andernfalls false

Einschränkungen

1 ≤ n ≤ 2³¹ - 1

Beispiele

Eingabe: n = 29
Ausgabe: true
Erklärung: Keine der Zahlen 2, 3, 4 oder 5 teilt 29, und 6 × 6 = 36 liegt bereits über 29, sodass kein weiterer Teiler mehr zu finden ist. 29 ist eine Primzahl.

Eingabe: n = 1
Ausgabe: false
Erklärung: Eine Primzahl hat genau zwei Teiler, 1 und sich selbst. 1 hat nur einen Teiler, daher lautet die Antwort false.

Eingabe: n = 91
Ausgabe: false
Erklärung: 91 sieht wie eine Primzahl aus, aber 7 × 13 = 91. Der Teiler 7 taucht auf, bevor die Suche √91 ≈ 9.5 überschreitet.

Weiterführende Frage

Jede Primzahl größer als 3 hat die Form 6k-1 oder 6k+1. Kannst du das nutzen, um nur ein Drittel der möglichen Teiler zu testen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Definition besagt, dass jeder Teiler von 2 bis n-1 ausgeschlossen werden muss; bei der größten Primzahl als Eingabe sind das über zwei Milliarden Divisionen. Teiler treten paarweise auf und ergeben miteinander multipliziert n; der kleinere Teiler jedes Paares ist höchstens √n. Du suchst also nur bis √n und musst höchstens etwa 23,000 ungerade Kandidaten prüfen.

Probiere jeden Divisor aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Die Definition liefert dir den Algorithmus. Eine Zahl n ≥ 2 ist prim, wenn keine der Zahlen 2, 3, ..., n-1 sie teilt. Prüfe jeden Kandidaten d mit n % d == 0 und gib beim ersten Teiler false zurück. Für 91 probiert die Schleife die Zahlen von 2 bis 6 aus und stoppt bei 7.

Behandle zuerst n < 2. Für n = 1 ist der Bereich der Kandidaten leer, sodass die Schleife nie einen Teiler finden und 1 als prim bezeichnen würde.

Zusammengesetzte Zahlen führen meist zu einem vorzeitigen Abbruch, aber eine Primzahl besteht jede Prüfung, sodass die Schleife bis zum Ende läuft. Für n = 2147483647, das eine Primzahl ist, sind das etwa 2.1 × 10^9 Divisionen – weit mehr, als in wenigen Sekunden möglich sind.

Algorithmus

Wenn n < 2, gib false zurück.
Durchlaufe d von 2 bis n-1.
Wenn n % d == 0, gib false zurück.
Gib nach der Schleife true zurück.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Probeteilung bis zur Quadratwurzel

Idee

Teiler treten paarweise auf. Wenn d n teilt, dann auch n / d, und beide multipliziert ergeben n. Sie können nicht beide größer als √n sein, denn dann wäre ihr Produkt größer als n. Wenn n also einen Teiler außer 1 und sich selbst hat, hat es einen, der höchstens √n ist. Bei 91 ist das Paar 7 und 13, und 7 ≤ 9.5. Wenn nichts bis einschließlich √n n teilt, tut es auch nichts darüber.

Schreibe die Grenze als d * d ≤ n, anstatt eine Quadratwurzelfunktion aufzurufen. So bleibt alles ganzzahlig, ohne Rundung. Das Gleichheitszeichen ist wichtig: 49 = 7 × 7, und der einzige Teiler 7 liegt genau bei √49.

Du kannst außerdem die Hälfte der Kandidaten überspringen. Behandle 2 separat: Ein gerades n ist nur dann prim, wenn es 2 ist. Danach hat ein ungerades n nur ungerade Teiler, also beginne bei 3 und erhöhe jeweils um 2. Für n = 2147483647 läuft die Schleife nun etwa 23,000 Mal statt 2.1 × 10^9 Mal.

Algorithmus

Wenn n < 2 gilt, gib false zurück.
Wenn n gerade ist, gib zurück, ob n == 2 gilt.
Setze d auf 3 und durchlaufe die Schleife, solange d * d ≤ n gilt. Verwende für d einen 64-Bit-Typ.
Wenn n % d == 0 gilt, gib false zurück. Andernfalls addiere 2 zu d.
Gib nach der Schleife true zurück.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Stolperfallen und Grenzfälle

Die Idee passt in eine Zeile. Die Fehler stecken an den Grenzen: bei den kleinsten Eingaben und beim letzten Teiler.

true für 1 zurückgeben. Es hat einen Teiler, nicht zwei, also ist es keine Primzahl.
2 ablehnen, weil es gerade ist. Prüfe n == 2, bevor du gerade Zahlen ausschließt.
Die Schleife mit d * d < n statt ≤ ausführen. Dann werden Quadrate von Primzahlen wie 9, 49 und 2147117569 = 46337² fälschlich als Primzahlen akzeptiert.
Überlauf bei d * d. In einem 32-Bit-int passt 46341 × 46341 = 2147488281 nicht hinein und wird zu einer negativen Zahl, sodass der Test weiterhin besteht und die Schleife weit über √n hinausläuft. Verwende für d einen 64-Bit-Typ oder vergleiche stattdessen d ≤ n / d.
Die Grenze mithilfe von sqrt mit Gleitkomma berechnen und das Ergebnis abschneiden. Ein double ist für jedes n hier exakt, aber bei 64-Bit-Eingaben kann die Rundung einen Wert ergeben, der um eins unter der tatsächlichen Wurzel liegt, wodurch der eine entscheidende Teiler übersprungen wird. d * d ≤ n birgt dieses Risiko nicht.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität für die Prüfung, ob eine Zahl eine Primzahl ist?

Die Probedivision bis √n benötigt O(√n) Zeit und O(1) Speicherplatz. Für n bis zu 2^31-1 sind das höchstens etwa 46,000 Divisionen oder 23,000, wenn gerade Teiler übersprungen werden. Jeden Teiler bis n-1 zu testen, ist O(n) und erfordert für die größte Eingabe etwa zwei Milliarden Schritte.

Warum prüfst du nur Teiler bis zur Quadratwurzel von n?

Teiler treten paarweise als d und n / d auf, deren Produkt n ist. Wären beide größer als √n, wäre ihr Produkt größer als n. Daher hat jedes Paar ein Element, das höchstens √n ist, und wenn bis dahin kein Teiler auftritt, ist n eine Primzahl.

Ist 1 eine Primzahl?

Nein. Eine Primzahl hat genau zwei verschiedene Teiler, 1 und sich selbst, und 1 hat nur einen. Wenn man 1 auslässt, bleibt die Primfaktorzerlegung jeder ganzen Zahl eindeutig. Deshalb gibt isPrime(1) false zurück.

def isPrime(n):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

n = 29

Erwartete Ausgabe

true