Prime factorization

Prime factorization writes a number as a product of primes, such as 60 = 2 · 2 · 3 · 5. A prime is a number greater than 1 whose only divisors are 1 and itself; 1 is not prime. Every number greater than 1 has exactly one such product, up to the order of the factors. Trial division factors one number up to about 10^{12} in about 10^6 tries, and the smallest-prime-factor array factors many numbers up to about 10^7.

Explanation

The school way to factor 60 is to keep dividing. 2 divides it twice, leaving 15, then 3 divides 15, leaving 5, and 5 divides itself. The numbers tried are 2, 3, 4 and 5, and 4 fails.

Fig. 1. 60 = 2 · 2 · 3 · 5. Grey marks numbers that were tried and did not divide.

The same method on 276 shows where the time goes. Dividing by 2 twice and by 3 once soon leaves 23. Then the method tries 4, 5, 6 and so on up to 22, and none of these 19 numbers divides 23. Only then does 23 divide itself, after 22 tries in total.

The method doesn't know when to stop, so it walks all the way up to the largest prime factor. For 1 999 999 874 = 2 · 999 999 937, it tries every number up to 999 999 937: 999 999 936 tries. By the rule of thumb from time complexity, about 10^8 simple steps per second, that is about 10 seconds for one number.

Fig. 2. Trying every number in turn, 23 is found only after 19 useless tries.

So the question is: when can we stop? Look at 23. If it were a product of two numbers bigger than 1, one of them would be at most 4, because 5 · 5 = 25 is already bigger than 23. 2, 3 and 4 have been tried and failed, therefore 23 is prime. The same holds for any number: once the next number to try, times itself, is bigger than what is left, what is left is prime. On 276 that is 3 tries instead of 22, and for 2 · 999 999 937 it is 31 621 tries instead of 999 999 936.

This is trial division: divide out 2, 3, 4 and so on in turn, stop at the square root of what is left, and keep the leftover if it is more than 1.

The outlined number is what is left, 276, and the green row below collects the prime factors; none is found yet, and the first number to try is 2.

Divide it out: 2 divides 276, so 2 is written down and 138 is left.

Divide it out again: 2 divides 138, so 2 is written down and 69 is left.

Try the next number: 2 no longer divides 69; the next is 3, and 3 · 3 = 9 ≤ 69, so the loop goes on.

Divide it out: 3 divides 69, so 3 is written down and 23 is left.

Try the next number: 3 no longer divides 23; the next is 4, and 4 · 4 = 16 ≤ 23, so the loop goes on.

Try the next number: 4 does not divide 23: every 2 was divided out before.

Stop at the square root of what is left: the next number is 5, and 5 · 5 = 25 > 23, so the loop ends.

Keep the leftover: 23 > 1, so 23 is prime and is written down: 276 = 2 · 2 · 3 · 23.

1/9

Fig. 3. Step through with the buttons or the arrow keys. Green numbers are prime factors found so far.

The run gives the whole factorization, 276 = 2 · 2 · 3 · 23, in 3 tries. The loop never goes past the square root of the original number, so a number below 2^{31} needs at most about 46 340 tries, about 0.5 ms. The slowest inputs are large primes, which never shrink: 2 147 483 647 takes 46 339 tries, while 2^{30} takes 1.

Factoring many numbers

Some problems ask to factor 10^6 numbers, each up to 10^7. Trial division takes up to about 3 161 tries for one such number (9 999 991 is a prime), so that is up to about 3 \cdot 10^9 tries in total.

The sieve of Eratosthenes can store, for each number, its smallest prime factor: the first prime to reach a cell writes itself there. 30 is first reached by 2, and 25 by 5. To factor a number, follow the smallest prime factors. One step reads the smallest prime factor, writes it down and divides the number by it; repeat until 1 is left. For 28, the smallest prime factor is 2, so 2 is written and 14 is next. 14 gives 2 again, and 7 is next. 7 is prime, so its smallest prime factor is 7 itself, and 1 is left: 28 = 2 · 2 · 7.

Fig. 4. Each number keeps its smallest prime factor. 28 = 2 · 2 · 7 is read off in three steps.

The sieve runs once, in about 0.06 seconds and 40 MB for all numbers up to 10^7. Each step at least halves the number, so after the sieve 10^6 numbers take at most about 2.3 \cdot 10^7 steps instead of 3 \cdot 10^9 tries.

Counting divisors

The factorization tells how many divisors a number has. In 276 = 2 · 2 · 3 · 23 the 2 appears twice: its exponent is 2, and the factorization is written 276 = 2^2 \cdot 3 \cdot 23. A divisor of 276 is a product of some of these factors. It takes 2 zero, one or two times: 3 choices. It takes 3 zero times or once: 2 choices. And it takes 23 zero times or once: 2 choices. So 276 has 3 · 2 · 2 = 12 divisors, and they are all different, because each number has only one factorization. In general, multiply together each exponent plus 1.

Fig. 5. Every divisor of 276 is a choice of how many 2s, 3s and 23s to take: 3 · 2 · 2 = 12.

Implementation

In code, what is left is n and the number tried is d. Both are long long, so that d * d can't overflow. The loop condition uses the current n, which shrinks as factors are divided out.

1. Try the next number: d = 2, 3, 4 and so on.

2. Divide it out: while n % d == 0, print d and set n /= d.

3. Stop at the square root of what is left: the loop ends when d * d > n.

4. Keep the leftover: if n > 1, then n is a prime factor; print it.

The program reads one number n (at least 1) and prints its prime factors in ascending order, separated by spaces; for 1 it prints an empty line. For the main example the input is:

276

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    for (long long d = 2; d * d <= n; d++) {   // try the next number; stop at the square root of what is left
        while (n % d == 0) {                    // divide it out
            cout << d << ' ';
            n /= d;
        }
    }
    if (n > 1) cout << n;                       // keep the leftover
    cout << '\n';
}

Trial division takes O(\sqrt{n}) time and $O(1)$ memory. For n up to 10^{12} that is about 10^6 tries, which fits in a second.

Many numbers with smallest prime factors

The sieve fills a vector<int> spf, the smallest-prime-factor array: spf[k] is the smallest prime factor of k. A cell that is still 0 when the outer loop reaches it belongs to a prime i, so spf[i] = i. Then i writes itself into every multiple from i * i on that has no factor yet.

1. Build the smallest prime factors: the sieve up to N.

2. Follow the smallest prime factors: while n > 1, print p = spf[n] and set n /= p.

The program builds spf up to N = 10^7, then reads numbers from 1 to N until the input ends and prints the prime factors of each on its own line (an empty line for 1). For the input 276 it prints the same factors as the program above.

#include <iostream>
#include <vector>
using namespace std;

const int N = 10000000;

int main() {
    // build the smallest prime factors
    vector<int> spf(N + 1, 0);
    for (int i = 2; i <= N; i++) {
        if (spf[i] == 0) {                       // i is prime
            spf[i] = i;
            for (long long j = (long long)i * i; j <= N; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }

    int n;
    while (cin >> n) {                           // 1 <= n <= N
        // follow the smallest prime factors
        while (n > 1) {
            int p = spf[n];
            cout << p << ' ';
            n /= p;
        }
        cout << '\n';
    }
}

The sieve takes O(N \log \log N) time: for N = 10^7 the inner loop runs 22 850 051 times, but each cell is written only once. spf takes 40 MB. After that, each number takes O(\log n) steps, so $q$ numbers take O(N \log \log N + q \log N) in total.

Correctness proof

Call what is left $n$ and the number tried $d$. When the loop reaches $d$, $n$ has no prime factor smaller than $d$. This holds at d = 2. When the loop moves on from $d$, the while has divided $d$ out until it no longer divides $n$, so it holds for d + 1 too.

Each $d$ that divides $n$ is prime. If $d$ were not prime, it would have a prime factor q < d, and $q$ would divide $n$ as well, which the fact above rules out. So every printed $d$ is a prime factor.

The leftover is prime. When the loop stops, d \cdot d > n. Suppose n > 1 and $n$ is not prime, so n = a \cdot b with 1 < a \le b. Every prime factor of $a$ divides $n$, so it is at least $d$, and so are $a$ and $b$. Then n = a \cdot b \ge d \cdot d > n, which is impossible. So the leftover is 1 or a prime. Together with the printed factors, it multiplies back to the original number, so the output is its factorization.

Following the smallest prime factors is correct because the smallest prime factor $p$ of $n$ is a prime that divides $n$. So n = p \cdot (n / p), and the factorization of $n$ is $p$ followed by the factorization of $n/p$. The loop repeats this until 1 is left. The sieve stores the smallest prime factor, because it handles the primes in increasing order and never overwrites a cell. A number $k$ that is not prime, with smallest prime factor $p$, has p \cdot p \le k, so the inner loop of $p$ reaches it.

Common mistakes

• Writing if instead of while. Each number is then divided out at most once, and 276 prints 2 3 46: 46 is not prime, but the leftover check takes it for one. Divide with while (n % d == 0).

• Building a smallest-prime-factor array for one big number. For one n up to 2 \cdot 10^9, an int array of that size takes 8 GB, while trial division needs at most about 46 340 tries.

Similar algorithms

When only primality is asked, the primality test runs the same loop up to the square root but stops at the first divisor and answers yes or no.

Listing divisors goes up to the square root and collects the pairs d and n / d, without dividing anything out. It is for problems that need the divisors themselves; their count alone comes from the exponents.

GCD and LCM don't need factoring: the Euclidean algorithm finds them in a few dozen steps for numbers up to 10^{18}. Factor only when the problem asks about the primes. A typical next use of the factors is Euler's totient, computed from the distinct prime factors.

The linear sieve fills the same smallest-prime-factor array in $O(n)$, writing each number once.

For numbers up to 10^{18}, trial division would need 10^9 tries; Pollard's rho factors them.

Practice