问题描述
在 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 中的素数迭代器的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!