Prime Factorization Calculator
Find the prime factors of any positive integer.
Understanding Prime Factorization
Prime factorization is the process of expressing a composite number as a product of its prime factors. Every integer greater than 1 is either a prime number itself or can be uniquely represented as a product of prime numbers (this is the Fundamental Theorem of Arithmetic).
What is a Prime Number?
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37...
Note that 2 is the only even prime number. All other even numbers are divisible by 2.
How to Find Prime Factors
The most common method is repeated division:
- Start with the smallest prime (2)
- Divide the number by 2 as many times as possible
- Move to the next prime (3, 5, 7, ...) and repeat
- Continue until the quotient becomes 1
Example: Factor 84
- 84 ÷ 2 = 42
- 42 ÷ 2 = 21
- 21 ÷ 3 = 7
- 7 ÷ 7 = 1
Result: 84 = 2 × 2 × 3 × 7 = 2² × 3 × 7
Applications of Prime Factorization
| Application | How It's Used |
|---|---|
| Cryptography (RSA) | Security relies on difficulty of factoring large numbers |
| Finding GCD/LCM | Compare prime factors of multiple numbers |
| Simplifying Fractions | Find common factors to reduce |
| Finding Divisors | Count divisors using exponents |
| Number Theory | Understanding number properties |
Counting Divisors
If a number n has prime factorization n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ, then the number of divisors is:
Example: 84 = 2² × 3¹ × 7¹ has (2+1)(1+1)(1+1) = 3 × 2 × 2 = 12 divisors
First 25 Primes
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Quick Divisibility Rules
- By 2: Last digit is even
- By 3: Sum of digits divisible by 3
- By 5: Ends in 0 or 5
- By 7: Double last digit, subtract from rest
- By 11: Alternating sum of digits = 0 or 11