Finding the Highest Prime Number for Sieving a Range
Die Frage in dem Bild lautet: „Nach welcher Primzahl kann bei einem Zahlenfeld bis 650 [2345] mit dem Streichen aufgehört werden? Begründen Sie.“
Die Aufgabe bezieht sich auf das Sieb des Eratosthenes, eine Methode, um Primzahlen bis zu einer bestimmten Grenze zu ermitteln. Bei dieser Methode werden beginnend mit der Zahl 2 alle Vielfachen von Primzahlen ausgestrichen, weil Vielfache von Primzahlen (außer der Primzahl selbst) keine Primzahlen sind.
Hier wird nach der höchsten Primzahl gefragt, nach deren Vielfachen man nicht mehr suchen muss, wenn man ein Zahlenfeld bis zur Zahl 650 [2345] betrachtet. Um diese Frage zu beantworten, müssen wir den größten Primfaktor finden, dessen Quadrat noch innerhalb der gegebenen Grenze liegt, da man nur bis zur Wurzel der größten Zahl im Feld streichen muss, um alle Nicht-Primzahlen zu identifizieren.
Die Wurzel von 650 ist etwa 25,5. Da wir nach einer Primzahl suchen, nehmen wir die nächstniedrigere Primzahl, die kleiner als 25,5 ist, und das wäre 23. Somit können wir nach dem Streichen aller Vielfachen von Primzahlen bis einschließlich 23 sichergehen, dass alle verbleibenden Zahlen bis 650 Primzahlen sind.
Die Begründung dafür ist, dass das Quadrat der nächsthöheren Primzahl, 29, bereits 841 ist, was über unserer Grenze von 650 liegt. Somit muss man keine Vielfachen von 29 oder größeren Primzahlen in unserer Liste streichen, um alle Primzahlen bis 650 zu finden.
Zusammengefasst kann beim Streichen in einem Zahlenfeld bis 650 nach der Primzahl 23 aufgehört werden.
