Prime Factorization Calculator
Break any positive integer into its prime factors. Shows the factorization in exponent notation with step-by-step division.
Results
Prime Factorization
Every integer greater than 1 can be expressed as a unique product of prime numbers. This is the Fundamental Theorem of Arithmetic. For example, 360 = 2³ × 3² × 5. No matter how you factor 360, you always end up with the same prime factors in the same counts.
How the Algorithm Works
Trial division: start with 2 (the smallest prime). Divide repeatedly until 2 no longer divides the number. Then try 3, then all odd numbers up to √n. If at any point the remaining quotient is greater than 1, it must itself be prime.
Uses in Mathematics
GCF: the product of common prime factors with minimum exponents. LCM: the product of all prime factors with maximum exponents. Fraction simplification: divide numerator and denominator by their GCF. Cryptography: RSA encryption relies on the fact that multiplying two large primes is easy, but factoring the product is extremely hard.
Worked Example: Factoring 360
Step 1: Divide by 2: 360 ÷ 2 = 180. Step 2: Divide by 2: 180 ÷ 2 = 90. Step 3: Divide by 2: 90 ÷ 2 = 45. Step 4: 45 is not divisible by 2. Try 3: 45 ÷ 3 = 15. Step 5: 15 ÷ 3 = 5. Step 6: 5 is prime.
Result: 360 = 2³ × 3² × 5. From this we can determine that 360 has (3+1)(2+1)(1+1) = 24 total divisors. This is a practical use of prime factorization in number theory.
Prime Factorization of Common Numbers
| Number | Prime Factorization | Number of Divisors |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 36 | 2² × 3² | 9 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 1000 | 2³ × 5³ | 16 |
| 1024 | 2¹⁰ | 11 |
Frequently Asked Questions
Writing a number as a product of primes. 12 = 2 × 2 × 3 = 2² × 3. The Fundamental Theorem of Arithmetic guarantees this representation is unique for every integer > 1.
Factorize both numbers, take each prime factor raised to the minimum exponent in either factorization, and multiply. GCF(12, 18): 12=2²×3, 18=2×3². GCF = 2¹×3¹ = 6.
Take each prime factor raised to the maximum exponent in either factorization and multiply. LCM(12, 18): 12=2²×3, 18=2×3². LCM = 2²×3² = 36.
No — every integer > 1 has a unique prime factorization (Fundamental Theorem of Arithmetic). If the number is prime, its factorization is just itself. 1 is a special case: it's the "empty product" with no prime factors.
RSA encryption, the standard for securing online communications, generates a public key by multiplying two large prime numbers (each with hundreds of digits). While multiplication is instant, factoring the resulting product back into its two primes takes longer than the age of the universe with current computers — making the encryption secure.
If n = p₁^a × p₂^b × p₃^c..., the total number of divisors is (a+1)(b+1)(c+1)... For 360 = 2³ × 3² × 5¹, divisors = (3+1)(2+1)(1+1) = 24. This formula only works after you have the complete prime factorization.
Use trial division: test primes in order (2, 3, 5, 7, 11, 13...) up to the square root of the number. You only need to test up to √n because if n has a factor larger than √n, it must also have a factor smaller than √n that you would have found first. For most numbers below 10,000 this can be done quickly by hand.