找到所有先前的下一个素数

我正在写一个递归无限素数生成器,我几乎可以肯定我可以更好地优化它.

现在,除了前十几个素数的查找表之外,每次调用递归函数都会收到所有先前素数的列表.

因为它是一个懒惰的生成器,所以现在我只是过滤掉任何以前的素数为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是作为匿名函数实现的,因此会破坏调用堆栈.

值得注意的是,我并不认为您需要所有先前的素数来生成下一个素数.由于我的实施,我碰巧有它们.