Hauptinhalt
Kurs: Informatik > Lerneinheit 2
Lektion 6: Primzahltest- Einführung
- Die Herausforderung des Primzahltests
- Test Division
- Was ist ein Computerspeicher?
- Algorithmische Effizienz
- Level 3: Challenge
- Sieb des Eratosthenes
- Level 4: Sieb des Eratosthenes
- Primzahltest mit einem Sieb
- Level 5: Probedivision mit einem Sieb
- Primzahlsatz
- Primzahl Spirale
- Primzahllücke
- Zeit-Speicher-Kompromiss
- Zusammenfassung (was kommt als nächstes?)
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Test Division
Definition des Problems
Wir müssen eine Maschine bauen, welche eine einfache Ja/Nein-Frage beantworten kann. Für eine Eingabe einer ganzen Zahl n, ist n eine Primzahl?
Lasst uns darüber nachdenken, wie das Innere dieser Maschine aussehen müsste, damit sie funktionierte. Maschinen können nur einer Abfolge von Schritten, basierend auf einigen Anweisungen, folgen (auch Algorithmus genannt). Lasst uns zum Aufwärmen herausfinden, welchem Algorithmus wir im Kopf folgen. Beantworte die folgende Frage: Ist 49 eine Primzahl?
…
Nein? Wie bist du zu diesem Ergebnis gekommen? Vermutlich hast du nach einem Teiler von 49 gesucht, welcher größer als 1 und kleiner als 49 ist. Wenn du die Multiplikationstabellen nicht auswendig kennst, würdest du natürlicherweise dieser Sequenz folgen:
- Ist 2 ein Teiler von 49? NEIN
- Ist 3 ein Teiler von 49? NEIN
- Ist 4 ein Teiler von 49? NEIN
- Ist 5 ein Teiler von 49? NEIN
- Ist 6 ein Teiler von 49? NEIN
- Ist 7 ein Teiler von 49? JA
Somit haben wir einen Teiler von 49 gefunden (7) und damit bewiesen, dass 49 eine zusammengesetzte Zahl ist.
Bau einer Mauer
Aber was passiert, wenn ich dich gefragt hätte ob 2971215073 eine Primzahl ist?
Überprüfst du noch? Nach den ersten paar tausend Tests habe ich immer noch keinen ' Divisor gefunden. Die Schlüsselfrage ist, wann können wir aufhören zu überprüfen und beweisen, dass n eine Primzahl ist? (lass uns dies unsere Wand nennen) Als Ausgangspunkt, muss unsere Mauer n-1 sein da n durch n teilbar ist. Wenn wir bis zu 2971215072 prüfen entweder finden einen entweder einen Divisor (was beweist dass n zusammengesetzt ist) oder nicht (was beweist dass n eine Primzahl ist ).
Wir bauen eine bessere Mauer
Das würde funktionieren, aber können wir unsere Mauer bewegen, um Zeit zu sparen? Erinnere dich daran, dass wir eigentlich auf der Suche nach dem ersten (oder kleinsten) sTeiler sind. Manchmal könnte der kleinste Teiler 2 sein, könnte aber auch viel größer sein. Dies bringt uns zu der Kernfrage: Wie groß könnte der kleinste Teiler sein?
Denke daran,, dass jede zusammengesetzte Zahl n aus zwei oder mehr Primzahlen zusammengesetzt ist n= P * P …
P ist am größten, wenn n genau zwei Teiler hat, die einander gleich sind. Dies bezeichnet man als Quadratzahl wie z. B. 9 (9 = 33) oder 49 (49 = 77) . Um diesen schlimmsten Fall zu erfassen bauen wir einfach unsere Mauer auf die Quadratwurzel von n!
Überzeugen Sie sich selbst davon: Wenn wir keinen Teiler von n finden bis zur Quadratwurzel von n, dann muss n eine Primzahl sein. Versuchen Sie, sich dies zu beweisen (ein Beweis dafür ist am Ende dieses Artikels)
Probe-Teilungsalgorithmus
Das ist es, wir können weitermachen. Lass uns zunächst unseren Teilungs-Testalgorithmus im Klartext aufschreiben:
- Akzeptiere die Eingabe einer ganzen Zahl n
- Prüfe für jede ganzen Zahl X von {2... sqrt(n)}, ob n durch X teilbar ist
- Wenn Sie einen Teiler gefunden haben, dann ist ist n eine zusammengesetzte Zahl gefunden ODER n ist eine Primzahl
Wenn du Erfahrung im Programmieren hast, solltest du Scratchpadöffnen und versuchen diese Funktion zum Laufen zu bringen. Ist dies nicht der Fall, können Sie mit dem nächsten Schritt fortfahren, wo ich eine Arbeitsversion für Sie als Ausgangspunkt bereitgestellt habe. (Zu Ihrer Information: Es ist möglich diese Lektion zu machen, ohne Programmierkenntnisse).
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.