Sieb des Eratosthenes - Streichen der Vielfachen |
| 15.01.2017, 10:10 | bine.c | Auf diesen Beitrag antworten » |
| Sieb des Eratosthenes - Streichen der Vielfachen Sieb des Eratosthenes Bei welcher Zahl kann man mit dem Streichen der Vielfachen aufhören, wenn man alle Primzahlen bis 1000 sucht? Begründen Sie! Wie viele Siebzahlen sind dann verwendet worden? Meine Ideen: n = 1000 Gestrichen werden müssen die echten Vielfachen aller Primzahlen p für die gilt Man kann mit dem streichen bei der Primzahl 31 aufhören. Die letzte Zahl die gestrichen werden muss ist die 961 (31*31) Es sind 11 Siebzahlen verwendet worden. Stimmt meine Lösung so? Ich habe in einer "Lösung" folgendes gefunden: Wenn man die Primzahlen bis 1000 finden möchte, so ist die letzte Zahl deren Vielfachen man streichen muss die 97. Die 98 und die 100 wurden schon beim Streichen der Vielfachen vn Zwei gestrichen und die 99 beim Streichen der Vielfachen von Drei. Alle Zahlen p kleiner 100 haben einen Komplementärteiler q, mit q ist kleiner 100 und wurden seit schon beim streichen der Komplementärteiler aussortiert. Diese Antwort verstehe ich nicht. Könnte es sein, dass meine Lösung stimmt? Vielen Dank schon im Vorhinein für eure Hilfe |
||
| 15.01.2017, 10:14 | 10001000Nick1 | Auf diesen Beitrag antworten » |
Deine Lösung ist richtig. Jeder Teiler einer Zahl bis 1000, der größer als ist, hat einen Komplementärteiler kleiner/gleich 31. Du hast also schon alle Nicht-Primzahlen gestrichen. Ging es in deiner Lösung vielleicht um die Primzahlen bis 10000? Da wäre 97 richtig. |
||
| 15.01.2017, 11:12 | bine.c | Auf diesen Beitrag antworten » |
Vielen Dank! Da bin ich beruhigt. LG |
||
|
|
