Diskussion:Sieb von Atkin
Falsche Formulierung
BearbeitenIch halte flgende Formulierung für falsch!
"Erstelle eine Siebliste mit einem Eintrag für jede positive ganze Zahl; alle Einträge dieser Liste werden am Anfang als nicht-prim markiert."
Hier stört mich das nicht, da in der weiteren Beschreibung des Algorithmus diese Aussage negiert beschrieben wird!
11:42, 26. Mär. 2007, von IP-Adresse 217.190.204.96 (falsch signierter Beitrag von 217.190.204.96 (Diskussion) 11:42, 26. Mär. 2007 (CEST))
Da es sich um einen neueren Autor handelt wäre ja wohl "Sieb von Atkin" der bessere Titel. --Claude J 14:10, 19. Aug. 2007 (CEST)
Optimiert?
BearbeitenWieso handelt es sich bei Atkin-Sieb eigentlich um eine Optimierung des Eratosthenes? Man muss zwar nur einen "etwas" kleineren Speicherbereich bearbeiten, aber in Bereichen wo diese Größe relevant wird, erkauft man sich diesen doch dann mit einer wesentlich größeren Laufzeit? --79.210.10.106 13:54, 21. Feb. 2010 (CET)
Stimmt??? Die Komplexität explodiert bei grossen N - was ist daran besser?? (nicht signierter Beitrag von 84.56.151.72 (Diskussion) 20:04, 27. Dez. 2010 (CET))
Erläuterung
BearbeitenLeider wird in dem Beitrag nicht auf die Herkunft von x und y eingegangen. Für einen Schüler wird es so unmöglich das Verfahren nachzuvollziehen. Aufschlussreich wäre eine grafische Darstellung in Form eines Ablaufdiagramms. (nicht signierter Beitrag von 188.110.76.215 (Diskussion) 18:12, 12. Feb. 2012 (CET))
Alle Zahlen, auch x und y, sind positive ganze Zahlen. Alle Zahlen mit Modulo 60 Rest 1, 13, 17, 29, 37, 41, 49, oder 53 haben einen Modulo 4 Rest von 1. Diese Zahlen sind genau dann prim, wenn die Anzahl an Lösungen für 4x² + y² = n ungerade ist und die Zahl quadratfrei ist.
n-y²=4x² daraus ergibt sich das n>y² und y ungerade sein muss, weil n-y² teilbar durch 4.
Laufzeit vom Sieb des Eratosthenes
BearbeitenIch dachte die Laufzeit vom Sieb des Eratosthenes beträgt O(n*log(log(n))) oder Irre ich mich? (nicht signierter Beitrag von 91.45.161.109 (Diskussion) 02:18, 10. Mär. 2012 (CET))
- Du irrst dich nicht, siehe engl. Wikipedia Seite zum Sieb des Eratosthenes.--95.91.63.4 09:09, 26. Okt. 2012 (CEST)
O Erklärung - völlig überflüssig
BearbeitenMuss man wirklich O als Landau Symbol benennen, was soll es denn sonst sein, was gängig oder verbreitet ist?--95.91.63.4 08:59, 26. Okt. 2012 (CEST)