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
Frequently asked questions
What is the prime factorization of a number?
It is the unique way of writing a positive integer as a product of prime numbers. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has exactly one such decomposition, ignoring the order of factors. For example, 360 = 2³ × 3² × 5.
How do you find the prime factors of a number?
Use trial division: starting with d = 2, divide the number by d repeatedly while it divides evenly, counting each division as the exponent, then move to the next divisor. You only need to test divisors up to √n — if anything greater than 1 remains after that, the remainder is itself a prime factor. This calculator performs the whole process instantly and shows both the exponent form and the expanded multiplication.
What is the prime factorization of 100?
100 = 2² × 5², that is, 2 × 2 × 5 × 5. Dividing by 2 twice gives 25, which is not divisible by 2 or 3, and dividing by 5 twice gives 1, ending the process. Since 100 has prime factors other than itself, it is a composite number.
Why is 1 not a prime number?
A prime is defined as a number with exactly two distinct divisors: 1 and itself. The number 1 has only one divisor, so it does not qualify. Excluding 1 also preserves the uniqueness of prime factorization — if 1 were prime, you could multiply by it any number of times and 360 would have infinitely many factorizations.
How is prime factorization used to find the GCD and LCM?
Factor both numbers, then for the GCD take each common prime raised to the smallest exponent, and for the LCM take every prime that appears raised to the largest exponent. For example, 360 = 2³ × 3² × 5 and 100 = 2² × 5², so GCD = 2² × 5 = 20 and LCM = 2³ × 3² × 5² = 1800.