sieb von atkin
-
hi ich würd gern das sieb von atkin implementieren, jedoch scheitere ich schon beim interpretieren des wikipedia-eintrags:
Alle Reste sind Modulo 60 Reste (der Rest nach einer Division durch 60 wird betrachtet).
Alle Zahlen, auch x und y, sind positive ganze Zahlen.
Im Folgenden bedeutet Invertieren eines Eintrags der Siebliste, dass dessen Markierung (prim oder nicht-prim) zum Gegenteil gewechselt wird.
1.Erstelle eine mit 2, 3 und 5 gefüllte Ergebnisliste.
2.Erstelle eine Siebliste mit einem Eintrag für jede positive ganze Zahl; alle Einträge dieser Liste werden am Anfang als nicht-prim markiert.
3.Für jeden Eintrag n in der Siebliste führe folgendes aus: Falls der Eintrag eine Zahl mit Rest 1, 13, 17, 29, 37, 41, 49, oder 53 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 4x² + y² = n.
Falls der Eintrag eine Zahl mit Rest 7, 19, 31, oder 43 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² + y² = n.
Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² − y² = n, wobei x > y.4.Beginne mit der niedrigsten Zahl in der Siebliste.
5.Nimm die nächste Zahl in der Siebliste, die immer noch als prim markiert ist.
6.Füge die Zahl in die Ergebnisliste ein.
7.Quadriere die Zahl und markiere alle Vielfachen von diesem Quadrat als nicht-prim.
8.Wiederhole die Schritte 5 bis 8.ich verstehe die abschnitte mit "falls der eintrag..." nicht. wie kann ich "ihn" für jede mögliche lösung invertieren? also wenn ich 2 lösungen der gleichung finde dann invertiere ich ihn zwei mal oder was?
-
oiausohdkjnyxf schrieb:
also wenn ich 2 lösungen der gleichung finde dann invertiere ich ihn zwei mal oder was?
Genau. Man will rausfinden, ob die Anzahl der Lösungen eine gerade oder ungerade Zahl ist.
-
sehr gut, danke dir.
-
nochmals eine folgefrage:
Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² − y² = n, wobei x > y.
die beiden ersten gleichungen waren einfach zu implementieren, diese hier aber gibt mir zu denken, denn x und y könnten ja beide auch riesengroß sein, daher fällt mir nicht ein wie man das hier in einer guten laufzeit lösen kann...
-
oiausohdkjnyxf schrieb:
nochmals eine folgefrage:
Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² − y² = n, wobei x > y.
die beiden ersten gleichungen waren einfach zu implementieren, diese hier aber gibt mir zu denken, denn x und y könnten ja beide auch riesengroß sein, daher fällt mir nicht ein wie man das hier in einer guten laufzeit lösen kann...
x und y können nicht beliebig groß werden.
Der kleinste Wert für 3x²-y² für festes x ensteht für y=x-1
und 3x²-(x-1)² wächst mit x, es gibt also eine (leicht zu ermittelnde) obere Schranke für x (und damit auch für y).
-
camper schrieb:
oiausohdkjnyxf schrieb:
nochmals eine folgefrage:
Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² − y² = n, wobei x > y.
die beiden ersten gleichungen waren einfach zu implementieren, diese hier aber gibt mir zu denken, denn x und y könnten ja beide auch riesengroß sein, daher fällt mir nicht ein wie man das hier in einer guten laufzeit lösen kann...
x und y können nicht beliebig groß werden.
Der kleinste Wert für 3x²-y² für festes x ensteht für y=x-1
und 3x²-(x-1)² wächst mit x, es gibt also eine (leicht zu ermittelnde) obere Schranke für x (und damit auch für y).oh man, wie dumm von mir. leuchtet natürlich ein.
danke euch beiden, implementierung scheint nun zu funktionieren.
-
oiausohdkjnyxf schrieb:
danke euch beiden, implementierung scheint nun zu funktionieren.
Miss mal, ob sie schneller oder langsamer als das Sieb des Eratostenes ist.
-
volkard schrieb:
oiausohdkjnyxf schrieb:
danke euch beiden, implementierung scheint nun zu funktionieren.
Miss mal, ob sie schneller oder langsamer als das Sieb des Eratostenes ist.
dazu musst du dich bis heute abend gedulden, habe hier kein gescheites tool zur hand...
-