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?
Denken Sie daran, dass jede zusammengesetzte Zahl n aus zwei oder mehr Primzahlen zusammengesetzt ist n= P * P …
P is largest when n has exactly two divisors which are equal to each other. This is known as a square number such as 9 (9 = 3*3) or 49 (49 = 7*7). To capture this worst case scenario we simply build our wall at the square root of 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).