Sieb des Eratosthenes < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:29 Sa 15.11.2008 | | Autor: | krischii |
Ich habe mich gerade in ein Problem verbissen und komme nicht weiter.
Ich beschäftige mich hin und wieder aus Langeweile mit Mathematik, weil es mir Spaß macht. Durch mein Biologiestudium habe ich auch ganz gute Grundlagen, was Statistik etc. angeht. Am folgenden Problem scheitere ich aber seit Stunden.
Aufgabe ist es mittels des "Sieb des Eratosthenes" Primzahlenrauszufinden, bzw. alle Nicht-Primzahlen bis 144 zu eliminieren. Die Zahlen sind dabei in 6er Reihen angeordnet. Soweit so gut, die Theorie dahinter habe ich verstanden und kann das auch mit Leichtigkeit lösen, leider verweifel ich an der "Extra-Aufgabe" die wie folgt lautet:
Nach Eliminierung der Vielfachen von 13 sind einige Zeilen bereits komplett eliminiert (91, 115, 121). Welche weitere Zeile wäre komplett eliminiert, würde man die Tabelle über 144 hinaus erweitern? Diese Reihe soll jedoch ermittelt werden, ohne die Tabelle tatsächlich weiterzuführen, d.h. mit geringstem Aufwand hergeleitet werden.
Für jede Idee, wie man das einfach lösen kann bin ich sehr dankbar.
Christian
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:21 Sa 15.11.2008 | | Autor: | Gilga |
nte Zeile:
6*n+1
6*n+2 // weg wegen 2
6*n+3 // weg wegen 3
6*n+4 // weg wegen 2
6*n+5
6*n+6 // weg wegen 3
also musst du nur noch untersuchen für welche n 6*n+1 und 6*n+5 durch deinen bisherigen Zahlen geteilt werden.
z.B. 6*n+5 wird durch 5 geteilt <=> n ist durch 5 teilbar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:01 So 16.11.2008 | | Autor: | reverend |
Nachdem Gilga das Problem so schön auf die Suche nach n und nur zwei Überprüfungen (6n+1, 6n+5) reduziert hat und dabei auch gleich die Primzahlen 2 und 3 abgefertigt hat, kannst Du Dir die Arbeit direkt noch weiter erleichtern.
Die weiteren Primzahlen, die bisher im Sieb angewandt wurden, sind 5,7,11,13. Alle vier haben (wie auch alle größeren Primzahlen) die Form [mm] 6k\pm1.
[/mm]
Nun hilft Dir eine Restklassenbetrachtung. Ich gebe Dir ein Beispiel mit der gar nicht gefragten [mm] 17=6*\blue{3}-1
[/mm]
Für Dein n ist nun die interessante Frage, welchen Rest es bei der Teilung durch [mm] \blue{3} [/mm] lässt. Es gibt ja nur drei Fälle:
1) n=3*i
2) n=3*i+1
3) n=3*i+2
Untersuchen wir nun jeweils 6n+1 und 6n+5 auf ihre Teilbarkeit durch 17 (bezüglich des Moduls 17). Vielleicht kennst Du die Schreibweise [mm] 19\equiv36\mod{17}, [/mm] die besagt, das 19 und 36 bei Teilung durch 17 den gleichen Rest lassen, zur gleichen Restklasse gehören, oder noch anders: im 17er-System die gleiche Endziffer haben. Dann findet man:
1a) [mm] 6n+1=6*3i+1=18i+1\equiv i+1\mod{17}
[/mm]
Deutung: bei n=3i ist 6n+1 genau dann durch 17 teilbar, wenn [mm] i\equiv 16\mod{17}, [/mm] also für i=16,33,50,67... Die ersten n, für die das gilt, sind also 48,99,150,201... Ab jetzt kürzer:
1b) [mm] 6n+5=6*3i+5=18i+5\equiv i+5\mod{17} \Rightarrow [/mm] n=36,87...
2a) [mm] 6n+1=6*(3i+1)+1=18i+7\equiv i+7\mod{17} \Rightarrow [/mm] n=31,82...
2b) [mm] 6n+5=6*(3i+1)+5=18i+11\equiv i+11\mod{17} \Rightarrow [/mm] n=19,70...
3a) [mm] 6n+1=6*(3i+2)+1=18i+13\equiv i+13\mod{17} \Rightarrow [/mm] n=14,65...
3b) [mm] 6n+1=6*(3i+2)+5=18i+17\equiv i\mod{17} \Rightarrow [/mm] n=2,53...
Das sieht erstmal kompliziert aus und wäre es auch für größere Primzahlen. Aber Du hast ja nur die Primzahlen 6-1,6+1,12-1,12-2 zu behandeln, da sind die Listen viel kürzer (und die möglichen n liegen enger beieinander).
Das ist sozusagen das Destillat des Siebs des Eratosthenes.
Du bekommst für Deine vier Primzahlen vier Listen möglicher n's. Und das gesuchte n muss in allen vier Listen stehen.
Probiers mal aus, es geht viel schneller, als es jetzt aussieht.
|
|
|
|
