primefactorization

Prime factorization is the process of expressing a positive integer greater than 1 as a product of prime numbers, each raised to a nonnegative integer exponent. The multiset of prime factors is unique: according to the Fundamental Theorem of Arithmetic, every such integer has a factorization n = p1^a1 p2^a2 ... pk^ak where the pi are distinct primes and the ai are positive integers. The factorization is unique up to the order of the factors. For 1, the concept is often left undefined or treated as the empty product.

Examples: 360 = 2^3 × 3^2 × 5; 84 = 2^2 × 3 × 7. Primes in the factorization are called the prime divisors of the number; the exponents indicate multiplicity.

Computing factorization begins with trial division, testing divisibility by primes in increasing order until the remaining quotient is 1. More efficient methods use the Sieve of Eratosthenes to generate primes up to sqrt(n). For large integers, specialized algorithms such as Pollard's rho, elliptic curve factorization, or the general number field sieve are used; these are nontrivial and not guaranteed to finish quickly. The difficulty of factoring large composites underpins the security of many cryptographic systems (for example RSA).

Prime factorization is used to compute gcd and lcm via exponents, simplify fractions, and study arithmetic properties. It also informs primality testing and various integer factorization problems.