我正在编写一个递归无限质数生成器，我几乎可以肯定我可以更好地优化它。
现在，除了前十二个质数的查找表外，每次调用递归函数都会接收之前所有质数的列表。
由于它是懒惰的生成器，现在我只是过滤掉任何模数为之前任何质数的结果，并取第一个未过滤的结果。(我使用的检查可以短路，所以第一次之前的质数将当前数字均匀地分割时，它会中止并返回信息。)
目前，我的性能在搜索第400个质数(37,813)时下降。我正在寻找使用我拥有所有先前质数的唯一事实，并仅搜索下一个来改进我的过滤算法的方法。(我可以找到的大多数信息提供非懒惰筛来查找极限以下的质数，或者通过给出pn-1的方式找到第pn个质数，而不是找到pn给出2...pn-1个质数的优化。)
例如，我知道第pn个质数必须驻留在(pn-1 + 1)...(pn-1+pn-2)范围内。现在我从pn-1 + 2开始对整数进行过滤(因为pn-1 + 1只能为质数，如果pn-1=2，则为预先计算的)。但由于这是一个懒生成器，知道范围(pn-1+pn-2)的终端边界并不能帮助我过滤任何东西。
在拥有所有先前质数的情况下，我可以做些什么来更有效地过滤？
这类似于一种惰性增量埃拉托斯特尼筛法。
您可以看到一些基本的优化尝试：我从pn-1+2开始检查，并跳过偶数。
我尝试了更直接的埃拉托斯特尼筛法，只需通过每个计算传递Integer.stream，并在找到质数后，在新的Stream.drop_while中包装Integer.stream，仅过滤掉那些质数的倍数。但由于Streams是作为匿名函数实现的，所以这破坏了调用栈。
值得注意的是，我并不假设您需要所有先前的质数来生成下一个质数。我只是碰巧拥有它们，感谢我的实现。
现在，除了前十二个质数的查找表外，每次调用递归函数都会接收之前所有质数的列表。
由于它是懒惰的生成器，现在我只是过滤掉任何模数为之前任何质数的结果，并取第一个未过滤的结果。(我使用的检查可以短路，所以第一次之前的质数将当前数字均匀地分割时，它会中止并返回信息。)
目前，我的性能在搜索第400个质数(37,813)时下降。我正在寻找使用我拥有所有先前质数的唯一事实，并仅搜索下一个来改进我的过滤算法的方法。(我可以找到的大多数信息提供非懒惰筛来查找极限以下的质数，或者通过给出pn-1的方式找到第pn个质数，而不是找到pn给出2...pn-1个质数的优化。)
例如，我知道第pn个质数必须驻留在(pn-1 + 1)...(pn-1+pn-2)范围内。现在我从pn-1 + 2开始对整数进行过滤(因为pn-1 + 1只能为质数，如果pn-1=2，则为预先计算的)。但由于这是一个懒生成器，知道范围(pn-1+pn-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）从流中发出它并2）将其添加到下一次调用中使用的质数堆栈的顶部。（我确定这个堆栈是某些减速的源头。）
next_primes函数接受该堆栈。从上一个已知质数+2开始，它创建一个无限的整数流，并丢弃每个可以被列表中任何已知质数均匀地整除的整数，然后返回第一个出现的值。这类似于一种惰性增量埃拉托斯特尼筛法。
您可以看到一些基本的优化尝试：我从pn-1+2开始检查，并跳过偶数。
我尝试了更直接的埃拉托斯特尼筛法，只需通过每个计算传递Integer.stream，并在找到质数后，在新的Stream.drop_while中包装Integer.stream，仅过滤掉那些质数的倍数。但由于Streams是作为匿名函数实现的，所以这破坏了调用栈。
值得注意的是，我并不假设您需要所有先前的质数来生成下一个质数。我只是碰巧拥有它们，感谢我的实现。
~n^1.43]（http://ideone.com/weY3dxhttp://ideone.com/weY3dx），生成了`n`个质数。SoE应该会快得多。 :) - Will Ness