找到m和n之间的所有整数，其平方除数之和本身就是一个平方
问题问题
42的除数是：1,2,3,6,7,14,21,42。这些除数的平方是：1,4,9,36,49,196,441,1764。平方除数的总和是2500这是50 * 50，一个正方形！
给定两个整数m，n（1 <= m <= n）我们想要找到m和n之间的所有整数，其平方除数之和本身就是一个平方。 42是这样的数字。
结果将是一个数组数组，每个子数组有两个元素，首先是平方除数为正方形的数字，然后是平方除数的总和。
代码如下
如何让这个特定的程序运行得更快？ 我的当前代码在n> 9999之后超时。
#returns the divisors of each number in an array of arrays r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} } #this finds all integers between m and n whose sum of squared divisors is itself a square squarenumbers = r.map { |x| x.map { |c| c**2 }.inject(:+) }.select { |x| Math.sqrt(x) % 1 == 0 } #returns an array of booleans. booleans = r.map { |x| x.map { |c| c**2 }.inject(:+) }.map { |x| Math.sqrt(x) % 1 == 0 } #returns the index of each of the true values in booleans as an array indexer = booleans.map.with_index{|x, i| i if x == true }.compact #returns the numbers whose squared divisors is a square in an array unsqr = indexer.map { |x| (m..n).to_a[x] } #merges the two arrays together, element for element and creates an array of arrays unsqr.zip(squarenumbers) # for m = 1 and n = 1000 the result would be # [[1, 1], [42, 2500], [246, 84100], [287, 84100], [728, 722500]] 首先计算：
m, n = 40, 42 r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} } #=> [[1, 2, 4, 5, 8, 10, 20, 40], [1, 41], [1, 2, 3, 6, 7, 14, 21, 42]]
没关系，但你不需要.to_a ：
r = (m..n).map { |z| (1..z).select { |x| z % x == 0} } #=> [[1, 2, 4, 5, 8, 10, 20, 40], [1, 41], [1, 2, 3, 6, 7, 14, 21, 42]]
这避免了额外的步骤，即创建临时数组：
(m..n).to_a #=> [40, 41, 42]
（ [*m..n] #=> [40, 41, 42] ：你也可以写[*m..n] #=> [40, 41, 42] 。）
为什么没有必要将范围转换为数组？ 可枚举#map是模块Enumerable的实例方法，可供include s Enumerable每个类使用。 Array是一个，但是(m..n).class #=> Range是另一个。 （参见Range的第二段）。
让我们倒退来提出我们的代码。 首先，如果q的因子的平方和本身是一个完美的平方，则集中精力确定任何给定数q 。 假设我们构造一个方法magic_number? 它将q作为唯一参数，如果q满足required属性则返回true否则返回false 。 然后我们将计算：
(m..n).select { |q| magic_number?(q) }
返回m和n之间满足属性的所有数字的数组。 magic_number? 可以像这样写：
def magic_number?(q) return true if q == 1 s = sum_of_squared_factors(q) s == Math.sqrt(s).round**2 end
所以现在我们留下编写方法sum_of_squared_factors 。 我们可以使用您的代码来获取因素：
def factors(q) (1..q).select { |x| q % x == 0 } end factors(40) #=> [1, 2, 4, 5, 8, 10, 20, 40] factors(41) #=> [1, 41] factors(42) #=> [1, 2, 3, 6, 7, 14, 21, 42]
然后写：
def sum_of_squared_factors(q) factors(q).reduce(0) { |t,i| t + i*i } end sum_of_squared_factors(40) #=> 2210 sum_of_squared_factors(41) #=> 1682 sum_of_squared_factors(42) #=> 2500
我们可以采取更多措施来加快因素的计算。 注意，数n每个因子f满足1 <= f <= n**0.5或nn**0.5 <= f <= n 。 此外，如果f是n的因子，则n/f是其“互补”因子。 （例如，因为3是因子42 ，所以42/3 #=> 14 ）。 因此，我们只需要检查哪些数字(1..n**0.5)是因子并包括它们的补充1 ：
q = 42 arr = (1..Math.sqrt(q)).select { |x| q % x == 0 } #=> [1, 2, 3, 6] arr.flat_map { |n| [n, q/n] } #=> [1, 42, 2, 21, 3, 14, 6, 7]
所以我们可以写：
def factors(q) arr = (1..Math.sqrt(q)).select { |x| q % x == 0 } arr.flat_map { |n| [n, q/n] } end
替换掉arr （“链接”表达式），我们获得了一个典型的Ruby语句：
def factors(q) (1..Math.sqrt(q)).select { |x| q % x == 0 }.flat_map { |n| [n, q/n] } end factors(42) #=> [1, 42, 2, 21, 3, 14, 6, 7]
（不需要对这个数组进行排序。在需要对其进行排序的应用程序中，只需将.sort flat_map在flat_map块的末尾。）
总之，我们留下以下内容：
def factors(q) (1..Math.sqrt(q)).select { |x| q % x == 0 }.flat_map { |n| [n, q/n] } end def sum_of_squared_factors(q) factors(q).reduce(0) { |t,i| t + i*i } end def magic_number?(q) return true if q == 1 s = sum_of_squared_factors(q) s == Math.sqrt(s).round**2 end m, n = 1, 1000 (m..n).select { |q| magic_number?(q) } #=> [4, 9, 25, 42, 49, 121, 169, 246, 287, 289, 361, 529, 728, 841, 961]
这个计算在眨眼之间就完成了。
我对这个众所周知的“诡计”毫不在意。
我不知道Ruby，但问题在于用于查找数字除数的算法（这不是特定于所使用的语言，即本例中的Ruby）。
r = (m..n).to_a.map { |z| (1..z).select { |x| z % x == 0} }
要找到整数n的除数，你要将n除以所有正整数n - 1 ，这意味着循环运行n - 1次。 但是，分割sort(n)以计算除数就足够了。 在伪代码中，这看起来如下：
for i = 1 to i <= sqrt(n) r = n % i if r == 0 then i is a divisor if n / i != i then n / i is another divisor
例如：
sqrt_42 = 6.48074069840786 i = 1 => 1 and 42 are two divisors i = 2 => 2 and 21 i = 3 => 3 and 14 i = 4 => no divisor i = 5 => no divisor i = 6 => 6 and 7
就这样。
这将大大提高性能，因为现在循环只运行sort(n)次而不是n - 1次，这对于大n是一个很大的区别。