Chr*_*ele 4 algorithm primes generator lazy-evaluation sieve-of-eratosthenes
我正在写一个递归无限素数生成器,我几乎可以肯定我可以更好地优化它.
现在,除了前十几个素数的查找表之外,每次调用递归函数都会收到所有先前素数的列表.
因为它是一个懒惰的生成器,所以现在我只是过滤掉任何以前的素数为0的任何数字,并取出第一个未经过滤的结果.(检查我正在使用短路,因此,当前一个素数首次将当前数字均分时,它会中止该信息.)
现在,我在搜索第400个素数(37,813)时性能下降.我正在寻找方法来使用我有一个所有先前质数列表的独特事实,并且我只搜索下一个,以改进我的过滤算法.(我能找到的大多数信息提供非懒筛找到下一个素数的限制,或方法来查找与p ñ个素数给定P N-1 ,不优化,求P ñ给出2.P N-1的素数. )
例如,我知道在p Ñ个素数必须驻留在范围(P N-1 + 1)...(P n-1个 + P N-2 ).现在我开始在p n-1 + 2 处对整数进行滤波(因为p n-1 + 1只能是p n-1 = 2的素数,这是预先计算的).但由于这是一个懒惰的生成器,知道范围的终端边界(p n-1 + p n-2)并没有帮助我过滤任何东西.
鉴于所有以前的素数,我能做些什么来更有效地过滤？
@doc """
Creates an infinite stream of prime numbers.
iex> Enum.take(primes, 5)
[2, 3, 5, 7, 11]
iex> Enum.take_while(primes, fn(n) -> n < 25 end)
[2, 3, 5, 7, 11, 13, 17, 19, 23]
"""
@spec primes :: Stream.t
def primes do
Stream.unfold( [], fn primes ->
next = next_prime(primes)
{ next, [next | primes] }
end )
end
defp next_prime([]), do: 2
defp next_prime([2 | _]), do: 3
defp next_prime([3 | _]), do: 5
defp next_prime([5 | _]), do: 7
# ... etc
defp next_prime(primes) do
start = Enum.first(primes) + 2
Enum.first(
Stream.drop_while(
Integer.stream(from: start, step: 2),
fn number ->
Enum.any?(primes, fn prime ->
rem(number, prime) == 0
end )
end
)
)
end
该primes函数以空数组开始,获取它的下一个素数(2最初),然后1)从Stream发出它并且2)将它添加到下一个调用中使用的素数堆栈的顶部.(我确定这个堆栈是一些减速的来源.)
该next_primes函数接收该堆栈.从最后一个已知的素数+ 2开始,它创建一个无限的整数流,并删除每个整数,该整数按列表的任何已知素数均匀划分,然后返回第一个匹配项.
我想这是类似于懒惰增量的Eratosthenes的筛子.
你可以看到一些基本的优化尝试:我开始检查p n-1 +2,然后我跳过偶数.
我只是通过每次计算传递Integer.stream来尝试更加逐字的Eratosthenes的筛子,并在找到一个素数之后,将Integer.stream包装在一个新的Stream.drop_while中,只过滤掉那些素数的多个.但是由于Streams是作为匿名函数实现的,因此会破坏调用堆栈.
值得注意的是,我并不认为您需要所有先前的素数来生成下一个素数.由于我的实施,我碰巧有它们.
对于任何数字k,您只需要尝试除了包括√k在内的素数.这是因为大于任何素√k需要与原相乘小比√k.
证明:
√k*√k= k so (a +√k)*√k> k(对于所有0 <a <(k-√k)).由此得出,如果存在小于√k的另一个除数,则(a +√k)除k.
这通常用于加速寻找素数.
当使用Eratosthenes算法的筛子从素数生成复合材料时,您不需要所有先前的素数,只需要那些低于当前生产点的平方根的素数就足够了.
这大大降低了内存需求.那么素数就是那些不在复合体中的奇数.
每个素数p从其正方形开始产生其倍数的链,以2p的步长枚举(因为我们仅使用奇数).这些具有其步长值的倍数存储在字典中,从而形成优先级队列.在该优先级队列中仅存在直到当前候选的平方根的素数(与E的分段筛的存储器要求相同).
象征性地,SoE是
P = {3,5,7,9,...}\U {{ p 2,p 2 + 2p,p 2 + 4p,p 2 + 6p, ...} | p in P }
每个(奇数)素数生成其倍数的流; 当所有这些流合并在一起时,我们拥有所有(奇数)复合数; 没有复合材料(和2),素数都是可能的.
在Python中(希望可以读作可执行的伪代码),
def postponed_sieve(): # postponed sieve, by Will Ness
yield 2; yield 3; yield 5; yield 7; # original code David Eppstein,
D = {} # ActiveState Recipe 2002
ps = (p for p in postponed_sieve()) # a separate Primes Supply:
p = ps.next() and ps.next() # (3) a Prime to add to dict
q = p*p # (9) when its sQuare is
c = 9 # the next Candidate
while True:
if c not in D: # not a multiple of any prime seen so far:
if c < q: yield c # a prime, or
else: # (c==q): # the next prime's square:
add(D,c + 2*p,2*p) # (9+6,6 : 15,21,27,33,...)
p=ps.next() # (5)
q=p*p # (25)
else: # 'c' is a composite:
s = D.pop(c) # step of increment
add(D,c + s,s) # next multiple, same step
c += 2 # next odd candidate
def add(D,x,s): # make no multiple keys in Dict
while x in D: x += s # increment by the given step
D[x] = s
一旦产生素数,它就会被遗忘.一个单独的主要供应来自同一个生成器的单独调用,递归地,以维护字典.而那个的主要供应也是从另一个中提取的,也是递归的.每个都需要仅提供到其生产点的平方根,因此总体上需要很少的生成器,并且它们的大小渐近无关紧要(sqrt( sqrt( N))等等).