julia - Julia 中的主要迭代器

Question

在 Julia 中是否有(高效的)迭代器来生成素数？内置函数 primes[N]生成直到 N 的所有素数一次，而不是按要求，并且在 N 时可能无法使用非常大，或未知。

Answer 1

您可以使用概率素性测试过滤通过(大)整数(Base.Count{BigInt} 迭代器)的计数器

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

那么例如

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

这总体上不如筛子那么有效，但不会在内存中保留巨大的结构。我记得 isprime使用标准的重复选择，至少没有高达 2^64 的误报。

编辑:

第二种可能性是生成(参见 Generator ) primes(N*(i-1)+1,N*i) 的块和 Base.flatten它们合并到一个列表中:

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