Julia的Prime Iterator

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