1

这是项目欧拉问题之一的（相当糟糕的）解决方案。问题是要找到第 10_001 个素数。下面的代码做到了，但运行需要 8 分钟。你能解释一下为什么会这样以及如何优化它吗？

primes = []
number = 2.0

until primes[10000] != nil
  if (2..(number - 1)).any? do |n|
    number % n == 0
  end == false
    primes << number
  end
  number = number + 1.0
end

puts primes[10000]
4

2 回答 2

7

素数发现的一些简单优化：

  • 首先将 2 推入素数列表，然后检查 3 是否为素数。（这消除了为数字 0 到 2 编写特殊情况代码的需要）

  • 您只需要检查主要候选人的奇数。（或者，如果您从添加 2/3/5 并检查 7 开始，则只需在执行 % 6 后检查 1 或 5 的数字。或者......你明白了）

  • 你只需要看看你当前的候选人x是否可以被直到 sqrt( x) 的因子整除——因为上面的任何因子都会sqrt(x)将 x 分成下面的数字sqrt(x)，并且你已经检查了所有这些。

  • 你只需要检查你的素数列表中的数字，而不是所有数字，x因为所有合数都可以被素数整除。例如，81 是 9*9 - 但 9*9 是 3*3*9，9 是合数，因此当您与 3 对比时，您会发现它是质数。因此，您永远不需要测试 9 是否是一个因数，依此类推，适用于每个复合因子。

有非常优化、加速的素数查找功能（请参阅阿特金筛法开始），但这些是很容易提出的常见优化。

于 2013-03-18T00:17:30.600 回答
1

您真的需要检查该数字是否与所有先前的数字相除吗？只检查你已经发现的较小的素数。另外，为什么在整数非常好的地方使用浮点数？

编辑：

一些可能的变化（不是最好的算法，可以改进）：

primes = [2, 3, 5]
num = 7

until primes[10000]
  is_prime = true
  i = 0
  sqrtnum = Math.sqrt(num).ceil
  while (n=primes[i+=1]) <= sqrtnum
    if num % n == 0
      is_prime = false
      break
    end
  end
  if is_prime
    primes << num
  end
  num += 2
end

puts primes[10000]

在我的电脑上（1000 个素数）：

 Yours:
real    0m3.300s
user    0m3.284s
sys     0m0.000s

 Mine:
real    0m0.045s
user    0m0.040s
sys     0m0.004s
于 2013-03-18T00:06:03.513 回答