1+2+...+n的约数(7) - 设想：我们还可以再快吗？

是的，我们还可以再快吗？我们还可以再快吗？
答案依旧是肯定的！
我们还有可以提高100甚至更多倍的质数求解算法！我们还有”避免重复运算“的重量级武器！

没有coding是完美的，没有做不到的，只有想不到的！

废话少说，让我们分析一下吧：
1. 质数的求解速度我们可以提高！特别是在更大的约数个数需求的时候。
我们可以预先用优化后的求解算法标记出某个范围以内的质数(用mark变量)，然后再需要的时候适当夸大这个运算范围（例如先10000以内，然后[10000, 20000]以内，等等）。当然我们仅仅把需要的质数放在primes的Array里。

代码:

def add_prime(n)    
   @primes << n if @mark[n]
end

不过，这需要很好的控制。

2. 我们并不需要特别地求解质数
注意一下，你就会发现，求解约数的过程和求解质数的过程很相似。
其实，它根本就包含着求解质数的过程。
我们可以省去那一部分的计算！

代码:

count *= 2 if (m != 1)新代码:if (m != 1)
      # @mark[m] = true # 注意这里，m是个质数！！！
      count *= 2
end

3. 重复计算？
是的！还有重复计算！
在num_of_divs_ex函数里，我们可以用循环求解并保存中间的值！

4. 我们可以换种思路吗？
当一种算法山穷水尽的时候，我们可以换种思路吗？
既然求约数个数的过程和求解质数的过程很像，那我们是不是可以用求解质数的优化算法来计算约数个数呢？

我们还可以再快吗？

 

（更多的coding我就不再贴出了）