Introduction

Prime factorization is the process of expressing an integer greater than one as a product of prime numbers. It is a basic number-theory concept, but it is also directly useful in programming for divisibility logic, greatest common divisor calculations, least common multiple calculations, and factor-based optimizations.

Why Prime Factorization Matters

The mathematical reason it matters is the fundamental theorem of arithmetic: every integer greater than one can be written as a product of primes in a way that is unique up to order.

For example:

• '84 = 2 * 2 * 3 * 7'
• '360 = 2 * 2 * 2 * 3 * 3 * 5'

You can reorder the factors, but you cannot replace them with a different set of prime factors and still get the same number. That uniqueness is what makes factorization useful for reasoning about divisibility and shared structure between integers.

Trial Division Is the Standard Starting Algorithm

For ordinary programming tasks, the standard algorithm is trial division. Repeatedly divide by the smallest factor you can find, beginning with 2, then continue with odd divisors.

1from collections import Counter
2
3
4def prime_factors(n: int) -> Counter:
5    if n <= 1:
6        raise ValueError("n must be greater than 1")
7
8    factors = Counter()
9
10    while n % 2 == 0:
11        factors[2] += 1
12        n //= 2
13
14    d = 3
15    while d * d <= n:
16        while n % d == 0:
17            factors[d] += 1
18            n //= d
19        d += 2
20
21    if n > 1:
22        factors[n] += 1
23
24    return factors
25
26
27print(prime_factors(360))

This algorithm is simple, correct, and fast enough for many moderate-size integers.

Format the Result Clearly

A factorization is often easier to read in exponent form than as a repeated list.

1from collections import Counter
2
3
4def format_factorization(factors: Counter) -> str:
5    parts = []
6    for p in sorted(factors):
7        exp = factors[p]
8        parts.append(f"{p}^{exp}" if exp > 1 else str(p))
9    return " * ".join(parts)
10
11
12f = prime_factors(360)
13print(format_factorization(f))

This prints 2^3 * 3^2 * 5, which is much easier to scan in explanations or logs.

Stop at the Square Root

The main optimization in trial division is to stop checking divisors once d * d > n. At that point, if the remaining n is greater than one, it must itself be prime.

That is why the algorithm does not keep scanning all the way up to the remaining number. This is also why skipping even divisors after handling 2 is a worthwhile improvement.

Without those two ideas, trial division becomes much slower than it needs to be.

Factors Help With GCD and LCM

Prime exponents give a clean way to think about greatest common divisor and least common multiple.

If:

• 'a = 2^3 * 3^2'
• 'b = 2^2 * 3^1 * 5^1'

then:

• the GCD uses the minimum exponent of each prime
• the LCM uses the maximum exponent of each prime

1from collections import Counter
2
3
4def merge_for_gcd_lcm(a: Counter, b: Counter):
5    primes = set(a) | set(b)
6    gcd_f = Counter()
7    lcm_f = Counter()
8
9    for p in primes:
10        gcd_f[p] = min(a.get(p, 0), b.get(p, 0))
11        lcm_f[p] = max(a.get(p, 0), b.get(p, 0))
12
13    return gcd_f, lcm_f

This is not how you would always implement GCD in performance-critical code, but it is a good way to understand why the arithmetic works.

Know the Practical Limits

Trial division is fine for small and medium inputs, but it is not a serious strategy for very large composite numbers, especially large semiprimes. For that you need more advanced algorithms such as Pollard rho or even heavier methods used in computational number theory.

That distinction matters because educational examples often make factorization look universally cheap. It is not. For large integers, factorization can be very hard.

Common Pitfalls

The first pitfall is treating 1 as prime or pretending it has a prime factorization. It does not. Another is forgetting to record the leftover n after the divisor loop ends.

Developers also often keep testing divisors long after the square-root stopping condition has made further checks unnecessary.

Finally, do not assume trial division scales to arbitrarily large integers. It is a practical baseline, not a universal large-number factorization method.

Summary

• Prime factorization writes an integer greater than one as a product of primes.
• Trial division is the standard practical starting algorithm.
• Stopping at the square root and skipping even divisors are important optimizations.
• Prime exponents help explain GCD, LCM, and divisibility rules.
• Large-number factorization requires more advanced algorithms than simple trial division.