Primzahltest bis sqrt(n)
Prüfen Sie eine einzelne Zahl effizient
Primzahltest bis sqrt(n) ist eine kostenlose Competitive Programming Academy-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 Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-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. ✅
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 Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Primzahltest bis sqrt(n)“?
Prüfen Sie eine einzelne Zahl effizient Du übst Competitive Programming Academy 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 Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy 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 Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-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