JUN
2009
Zum Tagesabschluß habe ich noch etwas heiteres, nämlich eine Suchanfrage: warum muss man bei primzahlen die vielfachen fon 11 nicht streichen?, will ein unbekannter Besucher wissen.
Da kann ich nur sagen: die Frage ist falsch gestellt. Wenn man mit dem Sieb des Eratosthenes Primzahlen bestimmen will, sind die Vielfacher von elf durchaus zu streichen -- genauso wie die aller anderen Primzahlen. Sind allerdings nur die Primzahlen bis N=100 gefragt, kann man nach der sieben aufhören: es genügt immer, bis zur Wurzel von N (hier also 10) zu prüfen.
Das sieht man so: angenommen, es gibt einen Teiler von n≤N (nennen wir ihn a), mit a>√N. Dann ist aber auch b = n/a ≤ N/a < N/√N = √N, also b<√N, Teiler von n; und so erkennen wir auch dann, daß n nicht prim ist, wenn wir nur bis √N prüfen.
Gute Nacht.
10.47 pm Kommentare deaktiviert für Gesiebtvon 
