Finding the Largest Prime Number to Stop Sieving
Um die Frage aus dem Bild auf Deutsch zu beantworten: Die Frage lautet „Nach welcher Primzahl kann bei einem Zahlenfeld bis 650 [2345] mit dem Streichen aufgehört werden?“
Für diese Aufgabe nutzen wir das Sieb des Eratosthenes, eine Methode zum Finden von Primzahlen. Man beginnt mit der kleinsten Primzahl, der 2, und streicht alle Vielfachen dieser Zahl im Zahlenfeld. Dieser Prozess wird mit der nächsten nicht gestrichenen Zahl, die eine Primzahl ist, fortgesetzt.
Da nach der größten Primzahl gefragt wird, bei der wir aufhören können, die Vielfachen zu streichen, um alle Primzahlen bis 650 zu finden, suchen wir die größte Primzahl, deren Quadrat kleiner oder gleich 650 ist. Dies deshalb, weil wenn \( p \) eine Primzahl ist, dann wurde das kleinste Vielfache von \( p \), das größer als \( p^2 \) ist und das wir entfernen müssten, nämlich \( p \cdot (p + 1) \), bereits als Vielfaches von \( p + 1 \) entfernt, wenn \( p + 1 \) keine Primzahl ist; oder es wird nicht entfernt, wenn \( p + 1 \) eine Primzahl ist.
Wir prüfen nun die Primzahlen und deren Quadrate:
\( 2^2 = 4 \) (zu klein)
\( 3^2 = 9 \) (zu klein)
\( 5^2 = 25 \) (zu klein)
\( 7^2 = 49 \) (zu klein)
\( 11^2 = 121 \) (zu klein)
\( 13^2 = 169 \) (zu klein)
\( 17^2 = 289 \) (zu klein)
\( 19^2 = 361 \) (zu klein)
\( 23^2 = 529 \) (zu klein)
\( 29^2 = 841 \) (zu groß, da größer als 650)
Also ist 23 die größte Primzahl, bei der wir aufhören können, da \( 23^2 = 529 \) ist und \( 29^2 = 841 \) bereits über dem Limit von 650 liegt. Wir können also bei der Primzahl 23 aufhören mit dem Streichen, wenn wir das Sieb des Eratosthenes bis 650 anwenden.
