Prime Factorization

Every integer greater than one has a unique product of prime powers, apart from factor order. This factorization exposes divisors, coprimality and multiplicative functions. Trial division is suitable for isolated moderate values; a smallest-prime-factor table pays a preprocessing cost to factor many bounded values quickly. We provide separate complete programs for both situations.

Prerequisites: Prime testing; Sieve of Eratosthenes.

Build the idea

1. 1. Record prime powers, not just prime names

   Write n as a product of pᵉ for distinct primes p. For 360, repeated divisions give 2³·3²·5. Keeping exponents matters: 12 and 18 have the same distinct prime set but different divisor counts. One has the empty prime factorization; zero and negative values are outside these examples’ contracts.

   $$n=\prod _{i=1}^k{p_i}^{e_i}$$

2. 2. Repeatedly remove the next divisor

   Try p from 2 while p≤remaining/p. If divisible, divide by p until no factor p remains and store its exponent. A divisor found this way must be prime: its smaller prime factors would already have been removed. The changing remaining value shortens later work. When remaining>1 after the loop it is a prime factor; if composite it would still have a small factor to test.

3. 3. Trace 360

   Dividing by 2 gives 180,90,45, so exponent 3. Dividing 45 by 3 gives 15,5, so exponent 2. Now p=4 is above 5/4; the remaining 5 is prime and gets exponent 1. Multiplying the recorded powers reconstructs 8·9·5=360, a useful correctness check independent of output formatting.

4. 4. Precompute smallest prime factors

   In the second program spf[x] stores x’s smallest prime factor. Discover p when its entry is zero, mark untouched multiples from p², and store spf[p]=p. To factor x, read p=spf[x] and repeatedly divide while p remains the smallest factor. Each division reduces x by at least two, so there are at most O(log x) divisions per query.

5. 5. Choose by query pattern

   A full SPF vector uses an integer entry for every value up to N, more memory than a prime flag. It is worthwhile for many queries x≤N; it does not factor arbitrary huge x beyond that range. Trial division avoids this shared table and handles the single 10^12-scale example, but repeated hard inputs can be slow. More advanced factorization for enormous integers needs other algorithms.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<utility>
int main(){
    long long n;
    std::cin>>n;
    std::vector<std::pair<long long,int>>factors;
    for(long long p=2;p<=n/p;++p){
        if(n%p==0){
            int exponent=0;
            do{
                n/=p;
                ++exponent;
            }
            while(n%p==0);
            factors.push_back({p,exponent});
        }
    }
    if(n>1){
        factors.push_back({n,1}); // Remaining factor is prime.
    }
    std::cout<<factors.size()<<'\n';
    for(auto[p,e]:factors){
        std::cout<<p<<' '<<e<<'\n';
    }
}

Complexity analysis

Trial division: O(√n) worst-case time and O(log(n+1)) factor-output storage as a safe bound; actual factor count is much smaller. The shown SPF sieve costs O(N log log N) time/O(N) memory, and each query uses O(log x) divisions plus output. This is an Eratosthenes-style SPF sieve, not a claimed linear sieve.

Example input and output

Trial program: read n, 1≤n≤10^12. Print the number of distinct prime factors, then each prime and exponent on its own line.

Input

360

Output

3
2 3
3 2
5 1

The factorization is 2³·3²·5, whose product is 360.

Read N q (1≤N≤10^7), then q values x in 1..N. Each output line contains factor count followed by prime/exponent pairs.

// Key idea: 3. Trace 360 Dividing by 2 gives 180,90,45, so exponent 3.
#include<iostream>
#include<vector>
#include<utility>
int main(){
    int N,q;
    std::cin>>N>>q;
    std::vector<int>spf(N+1,0);
    for(int p=2;p<=N;++p){
        if(spf[p]==0){
            spf[p]=p;
            if(p<=N/p){
                for(long long j=1LL*p*p;j<=N;j+=p){
                    if(spf[(int)j]==0){
                        spf[(int)j]=p;
                    }
                }
            }
        }
    }
    while(q--){
        int x;
        std::cin>>x;
        std::vector<std::pair<int,int>>factors;
        while(x>1){
            int p=spf[x],e=0;
            do{
                x/=p;
                ++e;
            }
            while(x>1&&spf[x]==p);
            factors.push_back({p,e});
        }
        std::cout<<factors.size();
        for(auto[p,e]:factors){
            std::cout<<' '<<p<<' '<<e;
        }
        std::cout<<'\n';
    }
}

Input

100 3
12
1
97

Output

2 2 2 3 1
0
1 97 1

12=2²·3; 1 has an empty factor list; 97 is prime.

Complexity: O(N log log N) preprocessing/O(N) memory; O(log x) divisions per query.

Practical applications

Use prime powers to derive divisor functions, totients, LCM/GCD formulas and modular reductions. Trial division fits isolated moderate values; SPF is strong for many values bounded by a common preprocessing maximum. If only primality is needed, a flag sieve may use less memory.

Check your understanding

What may remain after trial division stops with remaining>1?

Put it into practice

Factor every integer up to 1000 with both programs and compare reconstructed products.