Ruby。如何改进搜索数字范围的最小倍数的循环

Question

我需要处理这个任务：

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

我的解决方案如下所示：

all_numbers = []

1.upto(2600) do |j|
     1.upto(10) do |i|
            if j % i == 0 
                all_numbers << j
                end
     end
end

result = all_numbers.select{|element| all_numbers.count(element) > 9 }
p result[0]

这给了我正确的答案，但是如果我想检查 0..20 的范围并像这样更改代码：

all_numbers = []

1.upto(100000) do |j|
     1.upto(20) do |i|
            if j % i == 0 
                all_numbers << j
                end
     end
end

result = all_numbers.select{|element| all_numbers.count(element) > 19 }
p result[0]

回复太慢了（其实我都没有等那么久。。所以还没找到正确答案。。。）

有什么想法吗？非常感谢！

Answer 1

你从错误的角度攻击这个。您不是要搜索直到找到正确的数字，而是要计算数字。这基本上意味着查看结果需要整除的所有数字，找到它们的质因数，然后使用每个质数的最大幂。例如，找到第一个可被数字 1-6 整除的数字将是这样的：

1: ignore
2: prime factors 2**1
3: prime factors 3**1
4: prime factors 2**2
5: prime factors 5**1
6: prime factors 2**1, 3**1

所以，你的唯一素数是 2、3 和 5。2 是平方，其他都是一次方。将它们相乘，得到 2 * 2 * 3 * 5，即 60。对于 1-10 的情况再进一步计算，我们有：

7: prime factors 7**1
8: prime factors 2**3
9: prime factors 3**2
10: prime factors 2**1, 5**1

所以现在你的唯一素数的最大幂是 2**3, 3**2, 5**1, 7**1 乘以 2 * 2 * 2 * 3 * 3 * 5 * 7，得到 2520。你已经知道了。在数字 1-20 上使用这种方法比去每个数字更快地得到结果。

Ruby 有一个质数库，如果你被允许使用的话（假设这是一个硬件分配）。具体来说，prime_division 方法将基本上 return 主要因素以非常有用的方式解决这个特定问题。

Ruby。如何改进搜索数字范围的最小倍数的循环

Ruby. How to improve my loop that searches for the smallest multiple of ranges of numbers

ruby

loops

nested-loops