计算连续素数分解
Calculating successive prime factorizations
大家都知道因式分解很难。但是如果我想计算从 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。这会计算 a 中整数点的个数圆圈。从 Wolfram Mathworld 页面可以看出，有一个根据 n 的质因数分解计算 r(n) 的公式。
到目前为止，我采用了两种方法：
1) 计算满足 x^2 + y^2 = n 的点数，其中 0 < x < y，然后使用一些排列参数来找到 r(n)
2) 计算 n 的质因数分解（独立地，每次），并使用此信息计算 r(n)。
从实验上看，2) 似乎更快，但与第一种方法相比，它的扩展效果不佳，后者速度较慢，但并没有慢很多。我有兴趣计算 40 位 N 的 R(N) = r(n) 的 1 到 N 的总和。
另一种选择是使用埃拉托色尼筛法之类的东西来生成直到 N 的所有素数，然后以各种方式组合它们，计算从 2 到 N 的所有数字的素因数分解，并使用相同的方法公式如前。
有没有人知道这些选项中哪个最有效？ 1) 是最容易实施的，起步较慢，但可能扩展得很好。
即使 1) 是最快的，我仍然有兴趣学习生成从 0 到 N 的所有质因数分解的最快方法。
可以修改埃拉托色尼筛法以计算从 2 到 N 的所有数字的因式分解。不要只标记质数的倍数，而是在每个倍数从列表中删除数字时跟踪每个倍数。我在 my blog.
给出了完整的代码解决方案
大家都知道因式分解很难。但是如果我想计算从 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。这会计算 a 中整数点的个数圆圈。从 Wolfram Mathworld 页面可以看出，有一个根据 n 的质因数分解计算 r(n) 的公式。
到目前为止，我采用了两种方法：
1) 计算满足 x^2 + y^2 = n 的点数，其中 0 < x < y，然后使用一些排列参数来找到 r(n)
2) 计算 n 的质因数分解（独立地，每次），并使用此信息计算 r(n)。
从实验上看，2) 似乎更快，但与第一种方法相比，它的扩展效果不佳，后者速度较慢，但并没有慢很多。我有兴趣计算 40 位 N 的 R(N) = r(n) 的 1 到 N 的总和。
另一种选择是使用埃拉托色尼筛法之类的东西来生成直到 N 的所有素数，然后以各种方式组合它们，计算从 2 到 N 的所有数字的素因数分解，并使用相同的方法公式如前。
有没有人知道这些选项中哪个最有效？ 1) 是最容易实施的，起步较慢，但可能扩展得很好。
即使 1) 是最快的，我仍然有兴趣学习生成从 0 到 N 的所有质因数分解的最快方法。
可以修改埃拉托色尼筛法以计算从 2 到 N 的所有数字的因式分解。不要只标记质数的倍数，而是在每个倍数从列表中删除数字时跟踪每个倍数。我在 my blog.
给出了完整的代码解决方案