Ich versuche eine Funktion zu schreiben, die alle ungeraden Primzahlen von 1..n mit dem "Sieve of Sundaram" Algorithmus
Hier ist mein Versuch:
%Vor%Aber es gibt einige falsche Zahlen wie 9,15,21,25 usw.
%Vor%Was mache ich falsch?
Sundarams seidene Arbeiten konzentrieren sich auf die ungeraden Zahlen 2n + 1 und schließen diejenigen aus, die das Produkt von Zahlen sind.
Wenn zwei Zahlen multiplizieren, um eine ungerade Zahl zu bilden, müssen sie beide ungerade sein, also unsere Zahl 2n + 1 = (2i + 1) (2j + 1). Wenn wir das multiplizieren, erhalten wir 2n + 1 = 4ij + 2i + 2j + 1, was wir zu 2n = 4ij + 2i + 2j vereinfachen können, was wiederum vereinfacht zu n = 2ij + i + j. Also wollen wir n nicht, wenn wir es als 2ij + i + j schreiben können. Dies gilt für alle Zahlen i und j, aber es ist in Ordnung, diejenigen zu entfernen, bei denen i & lt; = j ist, weil Sie sonst die gleiche Zahl zweimal ausschließen.
In Ihrem Code generieren Sie einige Zahlen i + j + 2 * i * j , die ausgeschlossen werden sollen, aber Sie schließen tatsächlich nur i anstelle von i + j + 2 * i * j aus. Die j<-[f i] gibt Ihnen nur einen einzigen j -Wert in einer Liste und stattdessen alle Zahlen von i bis n , die Sie als [i..n] schreiben sollten.
Es ist viel einfacher, zuerst die Ausschlussliste zu generieren:
%Vor% Hier habe ich beschlossen, i und j zwischen 1 und n zu belassen, weil sonst 2ij + i + j definitiv größer ist als n.
Nun können wir eine Liste mit den Zahlen x erstellen, die diese Zahlen nicht enthalten, und sie dann mit der Formel 2*n+1 :
Was Sie richtig sagt
%Vor%Es ist jedoch nicht so schnell, wie es sein könnte, denn wenn man sich
anschaut %Vor% es hat Zahlen viel größer als wir brauchen - sSund 10 geht nur so weit wie 2 * 10 + 1 = 21. Das heißt, wir überprüfen unsere Zahlen immer wieder gegen Zahlen, die wir sowieso nicht berücksichtigt haben!
Am einfachsten ist es, sSundDelete neu zu schreiben, um
sehr viel wie du, oder
%Vor%Das Problem dabei ist, dass sie zu viele Zahlen generieren und sie dann wegwerfen. Es wäre schneller, nur die Zahlen zu generieren, die wir brauchen.
Eigentlich denke ich, es ist am besten zu berechnen, wie weit es gehen soll. das kleinste j , das wir jemals benutzen werden, ist i , also das kleinste, das 2ij + i + j sein kann, ist 2i 2 + 2i. Wenn wir nicht wollen, dass das über n ist, wollen wir 2i 2 + 2i & lt; = n, was wir als 2i (i + 1) & lt; = n umschreiben können. Korrektheit ist wichtiger als Effizienz, also ist es in Ordnung, n ein bisschen zu übergehen, aber es ist wichtig, Zahlen unter n nicht zu verpassen, also können wir 2i 2 & lt; = n sagen. Dies kann ausgedrückt werden als i <= floor (sqrt (fromIntegral n / 2)) ( floor schneidet Dezimalstellen ab, also floor 35.7 ist 35, und fromIntegral wird hier verwendet, um n in eine Fließkommazahl zu konvertieren (was Nicht-Ganzzahlen zulässt), so dass wir Division durchführen können und Quadratwurzeln.
Das war eine Menge Arbeit, aber jetzt können wir nur einmal berechnen, wie groß i gehen soll:
Wir können einen ähnlichen Job auf j machen. Wir wollen 2ij + i + j & lt; = n, die wir umordnen können, um zu sagen (2i + 1) j & lt; = n-i, was als j<=floor( (n'-i')/(2*i'+1)) , wo i'=fromIntegral i und n'=fromIntegral n gemacht werden kann. Das gibt uns
Das macht es schnell genug für mich, nicht aufzugeben und auf sSund 5000 zu warten, um die zweite Primzahl zu berechnen!
Tags und Links haskell list-comprehension sieve