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 nN (nennen wir ihn a), mit a>√N. Dann ist aber auch b = n/aN/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.

22:47 Kein Kommentar

von kirjoittaessani

Leave a Reply