算法 - 这个埃拉托色尼筛法解决方案有什么问题

Question

我想我会创建自己的 Sieve 算法实现以更快地找到素数。令人惊讶的是，这未能通过多项测试。

这是我在 Ruby 中用于确定数字是否为素数的算法。

def prime?(n)
  primes = [2,3,5,7,9,11,13,17]
  primes.include?(n) || primes.none? { |p| n % p == 0 }
end

算法的工作原理是你取前几个质数，我取前 8 个是安全的。然后我会剔除这些素数的所有倍数，因为它们不可能是素数。

因此所有其他数字都必须是质数

我很震惊地发现我的测试失败了，而且我忽略了一些数字。这怎么可能？我完全遵循算法。

Answer 1

首先，你在素数列表中包含了 9。 9不是素数。尝试以下方法。

找出给定数以内的所有素数。从最小的素数 2 开始。
标2为质数，剔除所有2的倍数。
接下来看，哪个是最小的没有被划掉的数。它是 3。打印 3 作为质数，并删除所有小于 n 的 3 的倍数。

然后再select下一个没有划掉的最小数字，依此类推

def primeSeive(n)
    while primes[index]**2 <= primes.last
        prime = primes[index]
        primes = primes.select { |x| x == prime || x%prime != 0 }
        index += 1
end

Answer 2

要测试给定数字 n 的素数，您需要检查它是否可以被任何 <= sqrt(n) 的素数整除。由于您已将最多 17 个素数硬连接到其中，因此您的算法仅适用于 n <= 17².

的值

最重要的是，您在 "primes" 的列表中包含了 9 个。这应该不会影响你的测试，除了值 9 本身，因为任何能被 9 整除的东西也能被 3 整除，但它很顽皮。

Answer 3

我不太擅长ruby，但您似乎没有遵循算法。您还添加 9 作为质数，这是不正确的。

在筛算法中一开始只需要2作为质数。

伪代码:

Sieve(n) {
  a[1] := 0                          
  for i := 2 to n do a[i] := 1
  p := 2
  while p2  <  n do {
    j := p2
    while (j  <  n) do {             
      a[j] := 0
      j := j+p
    }
    repeat p := p+1 until a[p] = 1   
  }
  return(a)
}

这里A是数组，其索引值表示素数。 0 对于 不是素数，1 对于素数。在 while 循环标记质数倍数，最后在 repeat 部分选择下一个质数。

算法 - 这个埃拉托色尼筛法解决方案有什么问题

Algorithm - What is wrong with this Sieve of Erastothenes solution

ruby

algorithm

primes

sieve-of-eratosthenes