为什么这段代码需要8分钟才能完成？

Question

这是项目Euler问题之一(非常糟糕)的解决方案.问题是找到10_001st素数.下面的代码可以实现,但运行需要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]

Answer 1

一些简单的优化来发现:

• 首先将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是复合的,所以当你检查它时你会发现它是一个素数.因此你永远不需要测试9是否是一个因素等每个复合因素.

有非常优化的,加速的主要查找功能(参见Atkin的Sieve开始),但这些是很容易想到的常见优化.