Prime Factorization Calculator

Prime Factorization Calculator - Decompose Numbers

🔢 Decompose any number into its prime factors. View results as product, with exponents, factor tree visualization, and step-by-step division process.

What is Prime Factorization?

Prime factorization (or integer factorization) is the process of breaking down a composite number into a product of prime numbers. Every composite number has a unique prime factorization.

Fundamental Theorem of Arithmetic

Every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. This is one of the most important theorems in number theory.

Factorization Formats

Product Form: 2 × 2 × 3 × 5

Exponential Form: 2² × 3 × 5

Index Form: 2² · 3¹ · 5¹

Factorization Examples

Example 1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• Prime factors: 2, 3

Example 2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• Prime factors: 2, 3, 5

Example 3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• Prime factors: 2, 5

Factorization Methods

1. Trial Division:

• Divide by smallest primes (2, 3, 5, 7...)
• Continue until quotient is 1
• Simple but can be slow for large numbers

2. Factor Tree:

• Break number into any two factors
• Continue breaking factors until all are prime
• Visual and easy to understand

3. Prime Division:

• Divide only by prime numbers
• More efficient than trying all numbers
• Standard algorithm for computers

Step-by-Step: Factoring 60

60 ÷ 2 = 30   (2 is prime)
30 ÷ 2 = 15   (2 is prime)
15 ÷ 3 = 5    (3 is prime)
5 ÷ 5 = 1     (5 is prime)

Result: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

Finding All Divisors

Once you have the prime factorization, you can find all divisors:

Example: 60 = 2² × 3¹ × 5¹

• For each prime, choose exponent from 0 to max
• 2⁰ or 2¹ or 2² → (1, 2, 4)
• 3⁰ or 3¹ → (1, 3)
• 5⁰ or 5¹ → (1, 5)
• Combine all possibilities
• Divisors: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Number of Divisors Formula

If n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Number of divisors = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

Example: 60 = 2² × 3¹ × 5¹

• Number of divisors = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12 divisors

Sum of Divisors Formula

Sum = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

Example: 60 = 2² × 3 × 5

• Sum = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

Applications of Prime Factorization

• Cryptography: RSA encryption relies on difficulty of factoring large numbers
• GCD/LCM: Find greatest common divisor and least common multiple
• Simplifying Fractions: Reduce to lowest terms
• Number Theory: Study properties of integers
• Computer Science: Hash functions, algorithms

Special Number Types

Perfect Numbers:

• Equal to sum of proper divisors
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

Abundant Numbers:

• Sum of proper divisors > number
• 12: divisors sum = 1+2+3+4+6 = 16 > 12

Deficient Numbers:

• Sum of proper divisors < number
• 8: divisors sum = 1+2+4 = 7 < 8

Powers of 2

Numbers that are powers of 2 have simple factorization:

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

Highly Composite Numbers

Numbers with more divisors than any smaller positive integer:

• 1 (1 divisor)
• 2 (2 divisors)
• 4 (3 divisors)
• 6 (4 divisors)
• 12 (6 divisors)
• 24 (8 divisors)
• 36 (9 divisors)
• 60 (12 divisors)

Difficulty of Factorization

• Small numbers: Easy to factor by hand
• Large primes: Very difficult to factor
• Semiprimes: Product of two primes, basis of RSA
• 200+ digits: Currently intractable with classical computers
• Quantum computers: Shor's algorithm can factor efficiently

Common Factorizations

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 Pro Tip: To quickly check if a number is divisible by small primes, remember these tricks: divisible by 2 if last digit is even; by 3 if sum of digits is divisible by 3; by 5 if last digit is 0 or 5; by 9 if sum of digits is divisible by 9; by 11 if alternating sum of digits is divisible by 11. For example, 4356: sum = 4+3+5+6 = 18 (divisible by 9), so 4356 is divisible by 9! Start factoring with these quick checks before trying larger primes.