ruby - Ruby 计算速度慢？欧拉计划#5

Question

这个问题引用了Project Euler 问题 5，所以要小心剧透！问题 5：

2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。能被 1 到 20 的所有数整除的最小正数是多少？

我在 Ruby 中编写了以下代码作为问题 5 的解决方案。

num = 2520
until (1..20).all?{|x| num % x == 0}
  num += 1
end
puts "#{num}"        

但是，每当我运行脚本时，它都会挂起。请注意，我在基本案例 2520 上测试了相同的方法，范围为 1 到 10，并且效果很好。

为什么它适用于更简单的情况，但不适用于更高级的情况？我能做些什么来修复我所拥有的？

Answer 1

这很慢，因为答案超过了 2 亿，而且您以 1 为步数数到它。这需要一段时间。你需要一个更好的算法。

Answer 2

您将无法像对待其他人那样暴力破解这个问题。您将需要为它找到更有效的解决方案。

下面的剧透

这是一种更有效的方法（如果这不是很像 Ruby，请道歉）：

def find_multiple
  lcm = 1

  (2..20).each do |i|
    lcm *= i / gcd(lcm, i)
  end

  lcm
end

def gcd(a, b)
  while b > 0
    a %= b
    return b if a == 0
    b %= a
  end

  a
end

puts find_multiple

如果您正在寻找一种更像 Ruby 的方法来解决它，您可以使用以下方法（正如 steenslag 在评论中所建议的那样）：

(1..20).inject(:lcm)

Answer 3

游戏有点晚了，但这是我的意见。如果你喜欢你的代码——简洁明了——你可以做一些小的调整来让它运行得更快。这对我有用而不会超时：

num = 20

  until (11..20).all?{ |i| num % i == 0 }
    num +=20
  end

puts num

本质上，您只需增加 20 秒，因为您知道它需要被 20 整除，并且您可以跳过对集合中较低 1/2 中的任何内容的迭代。

Answer 4

ruby 语言中最简单和干净的解决方案。

(1..20).inject(:lcm) # output will be 232792560

Answer 5

试试这个。代码：

i=2520
max_product = (4..19).inject(1){|j,k| j*k}
puts max_product
while i < max_product
    if( [3, 7].inject(true) do |memo, p|
        memo && i%p==0
    end)
      if( 
          (4..20).inject(true) do |memo, p|
          memo && i%p==0
          end 
      )   
      puts i
      end 
    end 
    i+=10
end