Prime Factorization Calculator
Find the prime factorization of any positive integer and check primality.
What Is the Prime Factorization Calculator?
To find the prime factors of a number, this prime factorization calculator divides the original number by each prime in sequence using trial division. The result, called a prime decomposition or factorization tree, expresses any integer greater than 1 as a unique product of primes. The Fundamental Theorem of Arithmetic guarantees this decomposition is unique. It is the foundation of GCD, LCM, and modern cryptography.
- ›Trial division, divide by 2, then 3, then all numbers of form 6k±1 up to √n. Record each prime divisor and reduce the original number. Any remaining factor greater than 1 is the final prime.
- ›Divisor count τ(n), from the prime decomposition p₁^e₁ × p₂^e₂, τ(n) = (e₁+1)(e₂+1). Example: 12 = 2²×3¹ gives τ(12) = 3×2 = 6 divisors.
- ›Euler's totient φ(n), counts integers from 1 to n coprime to n. Used in RSA encryption: the private key satisfies ed ≡ 1 (mod φ(n)).
- ›Common factor calculator mode, enter two numbers to find the GCD (highest common factor) and LCM from their prime factorizations side by side.
Formula
Fundamental Theorem of Arithmetic
Every integer n > 1 has a unique prime factorization:
n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ
Number-Theoretic Functions
τ(n) = (e₁+1)(e₂+1)⋯(eₖ+1) [divisor count]
σ(n) = ∏ (pᵢ^(eᵢ+1) − 1)/(pᵢ − 1) [sum of divisors]
φ(n) = n × ∏ (1 − 1/pᵢ) [Euler's totient]
GCD and LCM
GCD(a,b) = product of shared prime factors (minimum powers)
LCM(a,b) = GCD(a,b) × a × b / GCD(a,b), or: a × b / GCD(a,b)
| Symbol | Name | Description |
|---|---|---|
| τ(n) | Divisor count | Number of positive integers that divide n evenly |
| σ(n) | Sum of divisors | Sum of all positive divisors of n (including 1 and n) |
| φ(n) | Euler's totient | Count of integers 1..n that are coprime to n |
| GCD | Greatest common divisor | Largest number dividing both a and b |
| LCM | Least common multiple | Smallest number divisible by both a and b |
How to Use
- 1Choose "Factorize a Number" to find the prime factors of a number, or "GCD & LCM" to compare two numbers.
- 2Enter any integer from 2 to 1,000,000,000 and press Factorize (or Enter).
- 3The factorization tree result shows the prime decomposition in exponent notation, e.g. 48 = 2⁴ × 3.
- 4Scroll down to see the full list of prime factors, divisor count τ(n), sum of divisors σ(n), and Euler's totient φ(n).
- 5In GCD & LCM mode: enter two integers and press Factorize. The common factor calculator shows both factorizations, GCD, and LCM.
- 6Press Clear to reset and start a new calculation.
Example Calculation
Factorizing 360:
GCD and LCM of 48 and 36:
Perfect Numbers
A number is perfect if σ(n) = 2n (sum of all divisors = 2n, or sum of proper divisors = n).
- ›6 = 2 × 3 → σ(6) = 1+2+3+6 = 12 = 2×6 ✓
- ›28 = 2² × 7 → σ(28) = 1+2+4+7+14+28 = 56 = 2×28 ✓
- ›496 = 2⁴ × 31 (Mersenne prime) → perfect ✓
- ›Only even perfect numbers are known; no odd perfect number has been found
Understanding Prime Factorization
Why Prime Factorization Matters
Prime factorization is the foundation of number theory and modern cryptography. RSA encryption , the protocol securing most HTTPS connections, relies on the difficulty of factoring large numbers. A 2048-bit RSA key uses primes with ~308 decimal digits each. This prime numbers calculator works instantly for any integer up to one billion.
Everyday uses include simplifying fractions (find GCD via prime decomposition), scheduling problems (find LCM), and checking divisibility. The list of prime factors of a number reveals everything about its divisibility, perfect-number status, and how it interacts with other integers.
Prime Factorization of Common Numbers
Quick reference: prime factorization of 20, 48, and other frequently used numbers.
| n | Prime Factorization | τ(n) | φ(n) |
|---|---|---|---|
| 12 | 2² × 3 | 6 | 4 |
| 20 | 2² × 5 | 6 | 8 |
| 24 | 2³ × 3 | 8 | 8 |
| 36 | 2² × 3² | 9 | 12 |
| 48 | 2⁴ × 3 | 10 | 16 |
| 60 | 2² × 3 × 5 | 12 | 16 |
| 100 | 2² × 5² | 9 | 40 |
| 360 | 2³ × 3² × 5 | 24 | 96 |
| 1000 | 2³ × 5³ | 16 | 400 |
Frequently Asked Questions
What is the Fundamental Theorem of Arithmetic?
The Fundamental Theorem of Arithmetic (FTA) is the cornerstone of number theory:
- ›Existence, every integer n > 1 can be factored into primes. Proved by repeatedly dividing by the smallest prime factor until reaching 1.
- ›Uniqueness, the factorization is unique up to reordering. 12 = 2×2×3 = 3×2×2 are the same factorization, only the order differs.
- ›Why it matters, GCD = product of common prime factors (minimum exponents). LCM = product of all prime factors (maximum exponents). Divisibility tests reduce to checking prime factors.
- ›Counterexample in other rings, the FTA does not hold in all number systems. In Z[√−5], 6 = 2×3 = (1+√−5)(1−√−5), two different factorizations into irreducibles, motivating algebraic number theory.
What is Euler's totient function φ(n)?
Euler's totient is one of the most important functions in number theory:
- ›Definition, φ(n) = count of integers 1 ≤ k ≤ n with GCD(k,n) = 1. Equivalently: n × ∏(1 − 1/p) over distinct prime factors p of n.
- ›For prime p, φ(p) = p − 1. Every integer from 1 to p−1 is coprime to p. Example: φ(7) = 6.
- ›For prime power, φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ(1 − 1/p). Example: φ(8) = φ(2³) = 8 × ½ = 4.
- ›RSA encryption, RSA uses n = p×q. Key generation requires φ(n) = (p−1)(q−1). The private key d satisfies e×d ≡ 1 mod φ(n). Security relies on factoring n being hard.
How do you compute GCD from prime factorizations?
Prime factorizations give a visual and systematic way to find GCD and LCM:
- ›GCD rule, take each prime factor that appears in BOTH numbers, using the LOWER exponent. GCD(48, 36) = GCD(2⁴×3, 2²×3²) = 2²×3¹ = 12.
- ›LCM rule, take each prime factor appearing in EITHER number, using the HIGHER exponent. LCM(48, 36) = 2⁴×3² = 144.
- ›Key identity, GCD(a,b) × LCM(a,b) = a × b always. Verify: 12 × 144 = 48 × 36 = 1728 ✓
- ›Euclidean algorithm, for large numbers, the Euclidean algorithm (GCD(a,b) = GCD(b, a mod b)) is faster than full factorization. This calculator uses it for the GCD/LCM tab.
What is the divisor count τ(n)?
The divisor count function τ(n) is a multiplicative arithmetic function:
- ›Formula, if n = p₁^e₁ × p₂^e₂ × ⋯ × pₖ^eₖ, then τ(n) = (e₁+1)(e₂+1)⋯(eₖ+1). Multiply exponent+1 for every prime factor.
- ›Special cases, τ(p) = 2 for any prime (only divisors are 1 and p). τ(p²) = 3. τ(p³) = 4. τ(1) = 1 (1 has only one divisor: itself).
- ›Perfect squares, τ(n) is odd if and only if n is a perfect square. This is because for non-square n, divisors pair as (d, n/d) with d ≠ n/d; for perfect squares, √n pairs with itself.
- ›Highly composite numbers, numbers with unusually large τ(n). Ramanujan studied these: 12 has τ=6, which is more divisors than any smaller number. 360 has τ=24.
What does it mean for a number to be a perfect number?
Perfect numbers have fascinated mathematicians since ancient Greece:
- ›Definition, n is perfect if the sum of its proper divisors (divisors except n itself) equals n. Equivalently, σ(n) = 2n where σ is the sum-of-divisors function.
- ›Known even perfect numbers, 6, 28, 496, 8128, 33550336. They follow the pattern 2^(p-1)(2^p-1) where 2^p-1 is a Mersenne prime. This was proved by Euler.
- ›Abundance and deficiency, if σ(n) > 2n, n is abundant (e.g., 12: σ=28 > 24). If σ(n) < 2n, n is deficient (e.g., 10: σ=18 < 20). Most numbers are deficient.
- ›Odd perfect numbers, no odd perfect number has ever been found, and none exists below 10³²⁰⁰. Whether any exist is one of the oldest open problems in mathematics.
What is the sum of divisors σ(n) used for?
The sum-of-divisors function σ(n) has both theoretical and practical significance:
- ›Formula, for prime power pᵏ: σ(pᵏ) = 1+p+p²+⋯+pᵏ = (pᵏ⁺¹−1)/(p−1). For composite n, multiply over distinct prime factors (σ is multiplicative).
- ›Example, σ(360) = σ(2³×3²×5) = (2⁴−1)/(2−1) × (3³−1)/(3−1) × (5²−1)/(5−1) = 15 × 13 × 6 = 1170.
- ›Aliquot sequences, start with n, repeatedly replace n with σ(n)−n (sum of proper divisors). Some sequences reach 1 (perfect power or prime), some cycle (amicable pairs), some grow unboundedly.
- ›Amicable numbers, two numbers (a,b) where σ(a)−a = b and σ(b)−b = a. The smallest pair is (220, 284). Discovered by Pythagoras.
How is prime factorization used to simplify fractions?
Prime factorization makes fraction arithmetic transparent:
- ›Simplifying, divide both a and b by GCD(a,b). The result a/GCD, b/GCD is the fraction in lowest terms. Using factorizations: cancel matching prime factors from numerator and denominator.
- ›Adding fractions, find LCM(b₁, b₂) as common denominator. Multiply each fraction to reach this denominator, then add numerators. Example: 1/4 + 1/6: LCM(4,6)=12, so 3/12 + 2/12 = 5/12.
- ›Comparing fractions, a/b < c/d iff a×d < c×b (cross-multiply). Or convert to a common denominator using LCM.
- ›Efficiency, the Euclidean algorithm finds GCD faster than full factorization for large numbers, so calculators use it internally while showing factorizations for educational clarity.