如何更快地解决项目euler＃21？
原始问题
设d（n）定义为n的适当除数之和（小于n的数均匀分成n）。 如果d（a）= b并且d（b）= a，其中ab，则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之间的所有数字和它们对应的除数之和（即散列[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的任何提示也将非常感激。
您可以采取以下措施来改进算法：
1）计算除数时无需循环到n / 2。 停在sqrt（2）而不是。 到那时你已经找到了一半的除数; 另一半计算为n除以前半部分。
2）当您在哈希表中输入一个数字时，您可以立即检查它的友好双胞胎是否已经在哈希表中。 不需要两个哈希表，也不需要两个比较它们的嵌套循环。
函数d（n） （通常称为σ（n） ）是除数函数的变体，它具有一个重要的属性，可以让您更有效地计算它。 它是乘法函数 ，这意味着如果n = ab ，其中a和b是互质的，那么d（n）= d（a）d（b） 。
这意味着如果你可以计算d（p k ） ，其中p是素数，那么d（n）= d（p 1 k 1 ）… d（p r k r ） ，其中n = p 1 k 1 .. .p r k r是n的素因子分解。 事实上，事实certificated（p k ）=（p k + 1 – 1）/（p – 1） ，所以d（n） =Πi（p i k i +1 – 1）/（p i – 1）。
因此，要为所有1≤n≤10000有效地计算d（n） ，可以使用筛子计算所有n的主要因子分解，然后使用上面的公式使用素数分解来计算d（n） 。
完成后，您只需要一个简单的循环来计算所有n的总和，其中d（d（n）） = n 。
通过将筛分步骤与d（n）的计算相结合，甚至可以进一步优化这一点，但我将把它留作感兴趣的练习。 这个特定问题的大小不是必需的。
分析你的方法
你正在采取的方法是从分裂开始，找到它的除数，总结它们并存储它们。 你会注意到你用来找到除数的方法是天真的 – 我不是说这是一种侮辱; 它只是说你的方法不使用它可能提供的任何信息，并且只尝试每个数字以查看它是否为除数。 它通过使用模块划分来实现这一点，并且在几乎所有情况下，大多数候选人都未通过测试。
更具建设性的东西
考虑一下你是否从未尝试过像这样的测试失败的数字。 事实上，从除数开始并从那里积累红利就完全避开了这个问题。
你可以通过遍历每个<= 5000的数字来做到这一点。这些是你的除数，其倍数是你的红利。 然后将除数加到每个倍数的除数之和。
这种方法逐位处理总和; 当你通过每个除数时，你将有一个数组映射红利到除数。 从那里，您可以使用您已经拥有的方法在此列表中搜索友好数字。
分工是一个缓慢的过程。 在你的方法中你做了很多，因此你的程序很慢。
首先，在试图找到一个数字的所有除数时，你正在尝试所有除数不超过该数字的一半作为潜在的除数。 你可以通过不超过数字的平方根来改进。 如果一个数字可以被大于它的平方根的数字整除，则除法的结果将小于平方根。 这将消除一些不必要的分歧。
此外，如果一个数字不能被2分割，它也将不能被4,6,8等分割。最好除以素数并构建可能的除数。
但是，问题可以通过完全不进行划分来解决。
你可以“欺骗”并使用Ruby的stdlib素数： http ：//rbjl.net/37/euler-021.rb
Java中的另一个解决方案
static int sum_Of_Divisors(int n){ int limit = n; int sum = 0; for(int i=1;i set){ int sum = sum_Of_Divisors(n); if(sum_Of_Divisors(sum)==n && n!=sum){ set.add(sum); return true; } return false; } static long q21(){ long sum = 0; HashSet set = new HashSet (); for(int i=1;i<10000;i++){ if(!set.contains(i)){ if(isAmicable(i,set)){ set.add(i); } } } for(Integer i: set) sum+=i; return sum; }