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.

Q: Gibt es eine schnellere Möglichkeit, sehr große Zahlen auf ihre Primzahleigenschaft zu testen?

Für eine einzelne 32-Bit-Zahl ist die Probedivision bis √n schnell genug. Bei Zahlen mit Dutzenden von Stellen verwenden Programme den Miller-Rabin-Test, der einige modulare Potenzen prüft, statt Teiler auszuprobieren. Um alle Primzahlen bis zu einer Grenze aufzulisten, ist das Sieb des Eratosthenes effizienter, als jede Zahl einzeln zu testen.

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.

+15 versteckte Tests beim Einreichen

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 Fragen4

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.

Gibt es eine schnellere Möglichkeit, sehr große Zahlen auf ihre Primzahleigenschaft zu testen?

Für eine einzelne 32-Bit-Zahl ist die Probedivision bis √n schnell genug. Bei Zahlen mit Dutzenden von Stellen verwenden Programme den Miller-Rabin-Test, der einige modulare Potenzen prüft, statt Teiler auszuprobieren. Um alle Primzahlen bis zu einer Grenze aufzulisten, ist das Sieb des Eratosthenes effizienter, als jede Zahl einzeln zu testen.

Python

def isPrime(n):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 29

Erwartet

true