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

Question

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."

lp[i * pr[j]] = pr[j]; -> lp[i * pr[j]] = pr[j]; lp2[i * pr[j]] = i;. So now we have i == lp[i] * lp2[i] and i / lp[i] == lp2[i]. No need to divide to get next factor. — Stanislav Volodarskiy
– Stanislav Volodarskiy, Commented Jan 6, 2022 at 20:17

Will Ness · Accepted Answer · 2022-10-21 17:59:09Z

1

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.

edited Oct 21, 2022 at 17:59

Will Ness

71.6k10 gold badges105 silver badges192 bronze badges

answered Oct 15, 2022 at 4:23

oluckyman

1263 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related