Overview

Prime factorization is the process of expressing a positive integer as a product of prime numbers. According to the fundamental theorem of arithmetic, every integer greater than 1 has a unique factorization into primes, up to the order of the factors. The result can be written as a list of primes or using exponents for repeated factors (for example, 360 = 23·32·5). The operation is elementary in number theory and underlies many more advanced concepts.

Basic characteristics

Prime factors are the building blocks of integers: they are primes that multiply together to give the original number. Prime factorization terminates when all remaining factors are prime; the only divisors left beyond primes are 1 and the number itself. The factorization is unique, which makes primes analogous to atoms in chemistry for integers.

How to perform a prime factorization

Common beginner-friendly steps use trial division, testing whether small primes divide the number. A typical approach:

  1. Start with the smallest prime, 2. Divide repeatedly while the number is even.
  2. Proceed to the next primes (3, 5, 7, 11, ...) and divide as long as the divisor produces an integer quotient.
  3. Stop when the remaining quotient is 1 or a prime itself.

For guidance on the general idea see prime factorization and lists of primes such as smallest primes. For very large numbers, more advanced methods are used (see below).

Example: factorizing 1729

Apply trial division to 1729. It is odd, so 2 is not a divisor. Testing in order, 3 and 5 do not divide 1729. Division by 7 yields 1729 = 7 × 247. Next factor 247; it is not divisible by 2 or 3, but 13 divides it, giving 247 = 13 × 19. Both 13 and 19 are prime, so the complete prime factorization is 1729 = 7 × 13 × 19. Because no factor repeats, exponents are all 1 in this case.

Algorithms and computational aspects

For modest-size integers, trial division and optimized variants (wheel factorization, sieving for small factors) are sufficient. For large integers—hundreds or thousands of digits—specialized algorithms such as Pollard's rho, the quadratic sieve, and the general number field sieve are used. The difficulty of factoring very large semiprimes (products of two large primes) underpins the security of some cryptographic systems, which rely on the practical hardness of factorization rather than impossibility.

History, uses, and notable facts

Prime factorization has been studied for millennia; ancient mathematicians examined divisibility and primes, and the modern formalization rests on the uniqueness property proved in elementary number theory. Practical uses include simplifying fractions, computing greatest common divisors and least common multiples, analyzing multiplicative functions, and supporting cryptography. Notable facts include Ramanujan's interest in special numbers (for example, 1729 is the Hardy–Ramanujan taxi number, though that is a separate property) and the principle that every composite number has at least one prime factor not exceeding its square root, which guides trial division.

Prime factorization remains a fundamental and widely taught topic because it connects simple arithmetic to deeper mathematical structure and real-world applications.