Primzahltest bis sqrt(n)
Prüfen Sie eine einzelne Zahl effizient
Primzahltest bis sqrt(n) ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Primzahlfrage
Eine grundlegende mathematische Fähigkeit ist festzustellen, ob eine einzelne Zahl prim ist. Eine Primzahl hat genau zwei Teiler: 1 und sich selbst. Prüfen wir das schnell. 🔍
Die naive Prüfung
Sie könnten versuchen, n durch jede Zahl von 2 bis n minus 1 zu teilen. Das ist korrekt, aber bei großen n schmerzhaft langsam.
Der Quadratwurzel-Trick
Hier ist die entscheidende Erkenntnis: Sie müssen nur Teiler bis zur Quadratwurzel von n prüfen. Jenseits davon kann kein neuer Faktor mehr auftreten.
Warum die Quadratwurzel genügt
Teiler treten paarweise auf und ergeben multipliziert n. Wenn beide über der Quadratwurzel lägen, wäre ihr Produkt größer als n, was unmöglich ist.
Die Schleifengrenze
Erhöhen Sie i von 2 an, solange i mal i höchstens n ergibt. Mit i*i vermeiden Sie bei großen Ganzzahlen Gleitkommafehler durch sqrt.
while i * i <= n:
...Kleine Fälle behandeln
Zahlen kleiner als 2 sind niemals Primzahlen, weisen Sie sie daher sofort zurück. Diese Prüfung hält Ihre Hauptschleife übersichtlich und korrekt.
if n < 2:
return FalseDie vollständige Funktion
Fügen Sie alles zusammen: Weisen Sie kleine Werte zurück und prüfen Sie dann mögliche Teiler bis zur Quadratwurzel. Jede Division ohne Rest bedeutet, dass n zusammengesetzt ist.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueBeschleunigen Sie die Prüfung
Prüfen Sie 2 separat und testen Sie anschließend nur ungerade Zahlen. Das Überspringen gerader Zahlen halbiert den Aufwand ungefähr, ohne zusätzliche Komplexität.
if n % 2 == 0:
return n == 2Der Zeitaufwand
Dieser Test läuft in O(sqrt n)-Zeit. Für eine einzelne Zahl bis zu einer Milliarde sind das nur ungefähr 30.000 einfache Operationen.
Eine Zahl, nicht viele
Der Quadratwurzeltest eignet sich hervorragend für eine oder wenige Abfragen. Wenn Sie die Primzahleigenschaft für einen ganzen Bereich benötigen, ist ein Sieb deutlich schneller.
Vermeiden Sie die sqrt-Falle
Der Vergleich mit i*i statt mit math.sqrt umgeht Rundungsfehler, durch die Grenzwerte fälschlicherweise akzeptiert oder abgelehnt werden können.
Schnelltest
Überprüfen Sie die Grenze, die diesen Test schnell macht.
Zusammenfassung
Sie können jetzt eine Zahl in O(sqrt n)-Zeit auf Primzahleigenschaft prüfen, kleine Werte abweisen, gerade Zahlen überspringen und mit i*i exakt bleiben. ✅
Lerne Coding Interview Prep mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 90
- Lektionen
- 360
Häufig gestellte Fragen
Ist die Lektion „Primzahltest bis sqrt(n)“ kostenlos?
Ja — der vollständige Text von „Primzahltest bis sqrt(n)“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Primzahltest bis sqrt(n)“?
Prüfen Sie eine einzelne Zahl effizient Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Primzahltest bis sqrt(n)“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- GGT, KGV und der euklidische Algorithmus
- Primzahltest bis sqrt(n)
- Sieb des Eratosthenes
- Primfaktorzerlegung und Teiler