Julia 中的素数迭代器 [英] Prime Iterator in Julia

问题描述

在 Julia 中是否有一个(有效的)迭代器来生成素数?内置函数 primes[N] 一次生成直到 N 的所有素数，而不是按要求生成，并且当 N 为非常大，或未知.

Is there an (efficient) iterator to generate prime numbers in Julia? The inbuilt function primes[N] generates all primes up to N at once, rather than as required, and may not be usable when N is very large, or unknown.

推荐答案

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

You can filter a counter going through the (big) ints (the Base.Count{BigInt} iterator) using the probabilistic primality test

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 的误报.

This is not so effective in total as a sieve but does not keep a huge structure in memory. I recall that isprime has at least no false positives up to 2^64 with the standard choice of repetitions.

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

A second possibility is to generate (see Generator) chunks of primes(N*(i-1)+1,N*i) and Base.flatten them into a single list:

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

在这台机器上，这个迭代器实际上在计算前 10^9 个素数方面优于普通的 primes.

On this machine this iterator actually beats plain primes for computing the first 10^9 primes.

编辑 2:

使用 gmpz 的 nextprime 的迭代器.

An Iterator using gmpz's 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

这篇关于Julia 中的素数迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！