prime-factoring - 如何在没有除法的线性筛算法中寻找一个整数的因式分解？

Question

我学会了一种叫做“线性筛”的算法https://cp-algorithms.com/algebra/prime-sieve-linear.html能够在线性时间内得到所有小于 N 的素数。

这个算法有一个副产品，因为它有一个数组 lp[x]，它存储数字 x 的最小质因数。

所以我们可以按照lp[x]找到第一个质因数，继续除法得到所有因数。

同时，文章中也提到，借助一个额外的数组，我们可以不除法得到所有因子，如何实现？

文章说:“......此外，仅使用一个额外的数组将使我们在寻找因式分解时避免除法。”

Answer 1

该算法归功于 Pritchard。它是 Paul Pritchard: "Linear Prime-Number Sieves: a Famiy Tree", Science of Computer Programming, vol. 9 (1987), pp.17-35 中算法 3.3 的变体。 .下面是删除了不必要测试的代码，以及一个用于存储因子的额外向量:

for (int i=2; i <= N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back(i);
    }
    for (int j=0; i*pr[j] <= N; ++j) {
        lp[i*pr[j]] = pr[j];
        factor[i*pr[j]] = i;
        if (pr[j] == lp[i]) break;
    }
}

然后，为了得到一个数x的所有质因数，得到第一个质因数作为lp[x]，然后递归得到factor[x]的质因数，在lp[x] == x<之后停止。例如，x=20、lp[x]=2 和 factor[x]=10；然后 lp[10]=2 和 factor[10]=5；然后 lp[5]=5 我们就停止了。所以质因数分解是 20 = 2*2*5。