如何在线性筛（linear sieve）算法中无需除法完成整数因式分解

原文翻译：... 此外，仅需使用一个额外数组，我们就可以在查找因数分解结果时避免使用除法操作。

核心思路 #

我们只需要新增一个名为prev的额外数组，它的含义是：prev[x] = x / lp[x]，也就是x除以它的最小质因子之后得到的结果。这个值我们可以直接在线性筛的运行过程中计算得到，全程不需要用到除法操作。

线性筛的改造步骤 #

我们保留原来的最小质因子数组lp，新增prev数组，筛法的运行流程如下：

• 初始化长度为N的lp数组和prev数组，初始值均为0，同时初始化空的质数列表primes
• 遍历i从2到N-1：
  • 如果lp[i] == 0，说明i是质数：
    • 令lp[i] = i
    • 令prev[i] = 1
    • 将i加入primes列表
  • 遍历primes中的每个质数p：
    • 如果p > lp[i]或者p * i >= N，直接终止当前遍历
    • 令lp[p * i] = p
    • 令prev[p * i] = i

无除法分解的操作流程 #

筛法运行完成后，要分解任意小于N的正整数x，只需要按照以下步骤操作，全程不需要用到除法：

1. 当x > 1时，重复以下流程：
   • 取出当前x的最小质因子lp[x]，加入分解结果列表
   • 将x更新为prev[x]

举个实际例子，分解x=12：

• 初始x=12，lp[12]=2，记录2，x更新为prev[12]=6
• x=6，lp[6]=2，记录2，x更新为prev[6]=3
• x=3，lp[3]=3，记录3，x更新为prev[3]=1
• x=1，循环终止，得到分解结果[2,2,3]，完全没有用到除法操作

如果需要得到质因子的幂次形式，只需要在收集的时候统计连续相同质因子的出现次数即可。

内容的提问来源于stack exchange，提问作者Dachuan Huang