如何更快地解决欧拉项目#21？

原始问题

令 d(n) 定义为 n 的真因数之和（小于 n 的数能被 n 整除）。 如果 d(a) = b 且 d(b) = a，其中 a b，则 a 和 b 是友好对，并且 a 和 b 中的每一个称为友好数。

例如，220的真因数是1、2、4、5、10、11、20、22、44、55和110；因此 d(220) = 284。284 的真因数是 1、2、4、71 和 142；所以 d(284) = 220。

计算 10000 以下的所有友好数字的总和。

我通过生成 1 - 10000 之间的所有数字及其相应除数和（即 hash[220] = 284）的哈希值解决了这个问题。然后我将哈希中的项目与哈希的副本进行比较......无论如何，它有效，但需要很长时间。我怎样才能让它更快？

def proper_divs_sum num
  divs = [1]
  for i in 2..((num/2) + 1)
    if num % i == 0
      divs.push i
    end
  end

  divs_sum = 0
  divs.each do |div|
    divs_sum += div
  end
  return divs_sum
end

def n_d_hash_gen num
  nd_hash = {}
  for i in 1..num
    nd_hash[i] = proper_divs_sum(i)
  end
  return nd_hash
end

def amicables num
  amicable_list = []
  hash1 = n_d_hash_gen(num)
  hash2 = n_d_hash_gen(num)

  hash1.each do |item1|
    hash2.each do |item2|
      if item1 != item2 && (item1[0] == item2[1] && item2[0] == item1[1])
        amicable_list.push item1
      end
    end
  end
  return amicable_list
end

另外，我是 Ruby 新手，因此任何有关如何使其更像 Ruby 的提示也将不胜感激。

功能d(n)（通常称为σ(n)）是一个变体除数函数 http://mathworld.wolfram.com/DivisorFunction.html，它有一个重要的属性，可以让您更有效地计算它。它是一个乘法函数 http://en.wikipedia.org/wiki/Multiplicative_function，这意味着如果n = ab, where a and b是互质的，那么d(n) = d(a) d(b).

This means that if you can calculate d(p^k) where p is prime, then d(n) = d(p₁^k₁) ... d(p_r^k_r), where n = p₁^k₁...p_r^k_r is the prime factorization of n. In fact, it turns out that d(p^k) = (p^k+1 - 1) / (p - 1), so d(n) = ∏_i (p_i^k_i+1 - 1) / (p_i - 1).

所以要计算d(n)为所有人有效1≤ n≤ 10000，您可以使用筛子来计算所有的素因数分解n，然后利用上面的公式计算d(n)使用素因数分解。

完成此操作后，您所需要的只是一个简单的循环来计算所有的总和n为此d(d(n)) = n.

通过将筛分步骤与计算相结合，甚至可以进一步优化d(n)，但我会将其作为感兴趣的练习。对于这个特定问题的规模来说，这并不是必需的。