Prime Factorization Calculator
Prime factorization breaks any positive integer into a unique product of prime numbers. According to the Fundamental Theorem of Arithmetic, every integer greater than 1 has exactly one prime factorization (ignoring order). For example, 360 = 2³ × 3² × 5, meaning 360 equals 2 multiplied by itself three times, times 9, times 5.
Knowing the prime factors of a number is essential for finding the greatest common divisor (GCD) and least common multiple (LCM) of two numbers, simplifying fractions, and solving problems in number theory, cryptography, and computer science.
How it works
Trial division: for each divisor d starting at 2, repeatedly divide n by d while d divides n evenly, recording d and counting the divisions as the exponent. Continue with d+1 until d² > n; if n > 1 remains, it is itself a prime factor. Result: n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ.
Use cases
- Finding the GCD and LCM of two or more numbers
- Simplifying fractions to lowest terms
- Solving problems in number theory and abstract algebra
- Understanding RSA encryption, which relies on the difficulty of factoring large numbers
- Determining whether a number is prime or composite