Diskussion:Sieb von Atkin

Letzter Kommentar: vor 11 Jahren von Dart1976 in Abschnitt Erläuterung

Falsche Formulierung

Bearbeiten

Ich 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))Beantworten

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)Beantworten

Optimiert?

Bearbeiten

Wieso 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)Beantworten

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)) Beantworten

Erläuterung

Bearbeiten

Leider 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)) Beantworten

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.

--Dart1976 (Diskussion) 04:21, 6. Apr. 2013 (CEST)Beantworten

Laufzeit vom Sieb des Eratosthenes

Bearbeiten

Ich 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)) Beantworten

Du irrst dich nicht, siehe engl. Wikipedia Seite zum Sieb des Eratosthenes.--95.91.63.4 09:09, 26. Okt. 2012 (CEST)Beantworten

O Erklärung - völlig überflüssig

Bearbeiten

Muss 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)Beantworten