CODEWITHSUNDEEP
prime-factoringsieve-algorithm
Dachuan Huang
Dachuan Huang

Reputation: 181

How to look for factorization of one integer in linear sieve algorithm without divisions?

I learned an algorithm called "linear sieve" https://cp-algorithms.com/algebra/prime-sieve-linear.html that is able to get all primes numbers smaller than N in linear time.

This algorithm has one by-product since it has an array lp[x] that stores the minimal prime factor of the number x.

So we can follow lp[x] to find the first prime factor, and continue the division to get all factors.

In the meantime, the article also mentioned that with the help of one extra array, we can get all factors without division, how to achieve that?

The article said: "... Moreover, using just one extra array will allow us to avoid divisions when looking for factorization."

Upvotes: 3

Views: 195

Answers (1)

oluckyman
oluckyman

Reputation: 126

The algorithm is due to Pritchard. It is a variant of Algorithm 3.3 in Paul Pritchard: "Linear Prime-Number Sieves: a Famiy Tree", Science of Computer Programming, vol. 9 (1987), pp.17-35. Here's the code with an unnecessary test removed, and an extra vector used to store the factor:

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;
    }
}

Afterwards, to get all the prime factors of a number x, get the first prime factor as lp[x], then recursively get the prime factors of factor[x], stopping after lp[x] == x. E.g.with x=20, lp[x]=2, and factor[x]=10; then lp[10]=2 and factor[10]=5; then lp[5]=5 and we stop. So the prime factorization is 20 = 2*2*5.

Upvotes: 1

Related Questions