Juliaのプライムイテレータ

Question

ジュリアで素数を生成するための（効率的な）イテレータはありますか？組み込み関数primes[N]は、必要に応じてではなく、一度にNまでのすべての素数を生成し、Nが非常に大きい場合、または不明な場合には使用できない可能性があります。

Answer 1

あなたは、例えば

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

そして、確率的素数判定テストを使用して（大）int型（Base.Count{BigInt}イテレータ）を通過するカウンタをフィルタリングすることができ

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

これは、合計で非常に効果的ではありません篩としては巨大な構造を保持しません。 isprimeには、標準的な繰り返しの選択肢で、少なくとも2^64までの間違い陽性はないことを思い出してください。

編集：

第二の可能性を生成することである1つのリストにprimes(N*(i-1)+1,N*i)とBase.flattenそれらのチャンク（Generatorを参照してください）：このマシンで

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

このイテレータは実際のために、プレーンprimesを打ちます最初の10^9個の素数を計算する。

編集2：

アンイテレータgmpzさんnextprime使用。

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

Lazy.jlをチェックアウトすると、オンデマンドでプライム反復を行うことができます。それは未知の多数のために働く。前提条件は、上限より小さいすべての素数を使用し、それらを格納するスペースが必要であるということです。それらの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) 

コードを説明するために、まずisprime機能によって、（その時点ではまだ定義されていない）すべての素数primesのリストを使用して定義されすべての素数をnの平方根よりも小さく取って、いずれかがnを分けるかどうかをチェックし、結果を論理的に否定します。

primeは、filterがisprimeで、2以降のすべての整数にわたって定義されます。

n以下のすべての素数を得るには、takeの代わりに@>> primes takewhile(p -> p <= n)を実行します。

Answer 3

ストレージに保存するが、いくつかの非素数を与える代替方法の1つは、ホイールを使用することです（Wheel Factorizationを参照）。必要なのは、最後に見つかった番号を保存し、ホイール上の次の番号に移動することだけです。

たとえば、2と3を個別に処理します。そして、5から2と4を交互に追加します：5,7,11,13,15 ...結果の数値のストリームは、2と3の倍数を排除します。5つ以上の素数の倍数も排除する複雑なホイールがあります。

この方法では、非素数で割り切れる時間がかかりますが、必要な記憶容量は節約されます。素数が希少になると、すべての車輪の方が効率が悪くなります。システムの時間とストレージの制限を知ることができます。