计算逐次素因式分解

Question

每个人都知道分解是很困难的。但是如果我想要计算从2到N的每一个数的素因式分解呢？如果我们计算了2，n-1中每一个数的素数分解，如果一个数n有一个小素数因子，那么计算n的因式分解是容易的，因为大约73%的数可以被2、3或5整除。当然，有些情况下，例如当n是两个相似大小的素数的乘积时，仍然很困难，但平均来说，我们可以期望这个问题相当容易，因为我们只需要找到一个数的一个因子，就可以将我们的问题减少到我们以前解决的两个问题(即，分解d和n/d)。

我问这个问题是因为我感兴趣的是求正方形r( N ) (http://mathworld.wolfram.com/SumofSquaresFunction.html)之和，n的范围是0到N，它计算的是圆中整数点的数目。在Wolfram Mathworld页面上可以看到，关于n的素因式分解，r(n)有一个公式。

到目前为止，我已经采取了两种方法：

1)计数满足x^2 + y^2 = n，0

2)计算n的素因式分解(每次独立)，并利用这些信息计算r(n)。

从实验上看，2)速度似乎更快，但与第一种方法相比，它不是很好地扩展，第一种方法比较慢，但没有那么慢。我对计算40位数N的R(N) =从1到N的和很感兴趣。

另一种选择是使用Eratosthenes的筛子来生成所有素数到N，然后以各种方式组合它们，计算从2到N的所有数的素数因式分解，并使用与以前相同的公式。

有谁知道这些选项中哪一种最有效? 1)最容易实现，起步缓慢，但可能扩展得相当好。2)快速启动，不扩展，快速发现因素当然更难实现，但是如果修改为使用以前分解的回忆录，或者使用上面提到的一些素数生成技术，可能会做得很好。

即使1)是最快的，我仍然有兴趣学习生成从0到N的所有素因式分解的最快方法。

Answer 1

Eratosthenes的筛子可以被修改为计算从2到N的所有数的因式分解，而不是仅仅标记素数的倍数，当它从列表中找到一个数字时，要跟踪每个倍数。我在我的博客上给出了一个完整的代码解决方案。