Prime Iterator in Julia

Question

Gibt es einen (effizienten) Iterator, um Primzahlen in Julia zu generieren? Die eingebaute Funktion primes[N] erzeugt alle Primzahlen bis zu N auf einmal, anstatt wie erforderlich, und ist möglicherweise nicht verwendbar, wenn N sehr groß oder unbekannt ist.

Answer 1

Sie können einen Zähler filtern die (großen) Ints geht durch (der Base.Count{BigInt} Iterator) mit dem probabilistischen Primzahltest

iterprimes = filter(isprime,countfrom(big(2),1)) 

Dann zum Beispiel

julia> collect(take(iterprimes, 5)) 
5-element Array{Any,1}: 
    2 
    3 
    5 
    7 
11 

Dies ist nicht so effektiv, insgesamt als Sieb, behält aber keine große Struktur im Gedächtnis. Ich erinnere mich, dass isprime mit der Standardauswahl der Wiederholungen mindestens keine Fehlalarme bis zu 2^64 hat.

Edit:

Eine zweite Möglichkeit (siehe Generator) Stücke von primes(N*(i-1)+1,N*i) und Base.flatten sie in einer einzigen Liste zu erzeugen, ist:

Base.flatten(primes(1000000*(i-1)+1,1000000*i) for i in countfrom(1)) 

Auf dieser Maschine diese Iterator tatsächlich schlägt Ebene primes für Berechnen der ersten 10^9 Primzahlen.

Edit 2:

Ein Iterator gmpz ‚s nextprime verwenden.

type 
    PrimeIter 
end 
function nextprime(y::BigInt) 
    x = BigInt() 
    ccall((:__gmpz_nextprime,:libgmp), Void, (Ptr{BigInt},Ptr{BigInt}), &x, &y) 
    x 
end 
Base.start(::PrimeIter) = big(2) 
Base.next(::PrimeIter, state) = state, nextprime(state) 
Base.done(::PrimeIter, _) = false 
Base.iteratorsize(::PrimeIter) = Base.IsInfinite() 


> first(drop(PrimeIter(), 10^5)) 
1299721 

Answer 2

Sie können Lazy.jl auschecken, wodurch Sie eine erstklassige Iteration auf Anfrage erhalten. Es funktioniert für eine unbekannte große Anzahl. Die Annahme ist, dass Sie alle Primzahlen verwenden möchten, die kleiner als eine obere Grenze sind, und dass Sie den Platz zum Speichern von ihnen haben.

Zitat aus ihrer readme: -

# isprime defined in terms of the prime numbers: 
isprime(n) = 
    @>> primes begin 
    takewhile(x -> x<=sqrt(n)) 
    map(x -> n % x == 0) 
    any; ! 
    end 

# the prime numbers defined in terms of isprime: 
primes = filter(isprime, range(2)); 

take(20, primes) 
#> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71) 

den Code zu erklären, zunächst isprime Funktion definiert ist die Liste aller Primzahlen mit primes (die bisher noch nicht zu diesem Zeitpunkt definiert haben), durch Nehmen Sie alle Primzahlen, die kleiner sind als die Quadratwurzel von n, überprüfen Sie, ob eine davon n teilt, und verneinen Sie das Ergebnis logisch.

Dann ist prime definiert als filter von isprime über alle Ganzzahlen ab 2.

Um alle Primzahlen unter n zu erhalten, können Sie einfach @>> primes takewhile(p -> p <= n) statt take ausführen.

Answer 3

Eine Alternative, die bei der Lagerung spart, aber Ihnen einige Nicht-Primzahlen gibt, ist ein Rad zu verwenden, siehe Wheel Factorization. Sie müssen nur die letzte gefundene Nummer speichern und zur nächsten Nummer auf dem Rad wechseln.

Zum Beispiel behandeln Sie 2 und 3 einzeln. Dann von 5 addiere 2 und 4 abwechselnd: 5, 7, 11, 13, 15 ... Der resultierende Strom von Zahlen eliminiert alle Vielfachen von 2 und 3. Es gibt komplexere Räder, die auch Vielfache von 5 oder höheren Primzahlen eliminieren.

Diese Methode kostet einige Zeit durch Nicht-Primes, spart aber Speicherplatz. Alle Räder werden bei größeren Stückzahlen weniger effizient, da Primzahlen seltener werden. Sie kennen die zeitlichen und räumlichen Grenzen für Ihr System.