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

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

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

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