Prime Factorization Calculator
Enter a whole number to write it as a product of primes, with the divisions shown one by one, plus its divisors, number of divisors, sum of divisors and Euler totient.
What is prime factorization?
A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. The Fundamental Theorem of Arithmetic says that every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. For example 360 = 23 × 32 × 5, and no other combination of primes multiplies to 360.
Prime factorization is the key that unlocks many other quantities: the greatest common divisor and least common multiple, the number and sum of divisors, Euler's totient function, and the simplification of fractions and square roots.
How the calculator factors a number
First it uses trial division: it divides by 2, 3, 5, 7 and so on, as long as the divisor squared is not larger than what is left, and shows each division. If anything greater than 1 remains after the small primes are removed, that remainder is tested with the Miller–Rabin primality test. If it is composite, Pollard's rho algorithm is used to split it into smaller pieces, each of which is tested again.
Trial division is perfect for numbers up to about ten digits and for finding small factors of any number. Pollard's rho extends the practical range to numbers of around 25 to 30 digits, whose factors are not too large. Numbers built from two large primes of 40 digits or more are exactly what RSA relies on being practically impossible to factor, so the calculator stops with a message rather than running for hours.
Divisors, their number and their sum
Once n = p₁e₁ … pₖeₖ is known, the number of positive divisors is τ(n) = (e₁ + 1)(e₂ + 1)…(eₖ + 1), because each prime can appear in a divisor with any exponent from 0 up to its exponent in n. The sum of the divisors is σ(n), the product of the geometric sums 1 + p + … + pe. For 360 these give τ = 4 × 3 × 2 = 24 and σ = 15 × 13 × 6 = 1170. When n has at most 400 divisors the calculator lists them all.
Tips for exams and homework
To test whether a number is prime by hand you only need to try the primes up to its square root: for 391 that is 19, and 391 = 17 × 23 is found at 17. Quick divisibility rules help: a number is divisible by 3 if its digit sum is, by 9 if its digit sum is divisible by 9, by 5 if it ends in 0 or 5, and by 11 if the alternating sum of its digits is divisible by 11.
Worked examples
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
360
Prime factorization
2^3 × 3^2 × 5
Divisors τ(n)
24
sum of divisors σ(n) = 1170, φ(n) = 96
Step-by-step solution
Formula used
n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ (unique, by the Fundamental Theorem of Arithmetic)
τ(n) = ∏(eᵢ + 1), σ(n) = ∏ (pᵢ^(eᵢ+1) − 1)/(pᵢ − 1), φ(n) = ∏ pᵢ^(eᵢ−1)(pᵢ − 1)
CalculateTrial division by small primes
divide out each prime p while p × p ≤ remaining number
Divide by 2: 360 ÷ 2 = 180 ÷ 2 = 90 ÷ 2 = 45
Divide by 3: 45 ÷ 3 = 15 ÷ 3 = 5
Remaining number: 5
CalculateTest the remaining number for primality
Miller–Rabin test
5 is prime (the Miller–Rabin test with the first 13 prime bases is a proof for numbers of this size).
ResultPrime factorization
360 = 2^3 × 3^2 × 5
360 is composite.
CalculateNumber of divisors τ(n) and sum of divisors σ(n)
τ(n) = (e₁+1)(e₂+1)…(eₖ+1), σ(n) = ∏ (p^(e+1) − 1) / (p − 1)
τ = (3+1) × (2+1) × (1+1) = 24
σ = (2^4 − 1)/(2 − 1) × (3^3 − 1)/(3 − 1) × (5^2 − 1)/(5 − 1) = 1170
Euler totient φ(n) = 4 × 6 × 4 = 96
NoteAll 24 positive divisors
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
CheckVerify by multiplying back
2^3 × 3^2 × 5 = 360 ✓ equals n
3 599 (59 × 61)
Prime factorization
59 × 61
Divisors τ(n)
4
sum of divisors σ(n) = 3720, φ(n) = 3480
Step-by-step solution
Formula used
n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ (unique, by the Fundamental Theorem of Arithmetic)
τ(n) = ∏(eᵢ + 1), σ(n) = ∏ (pᵢ^(eᵢ+1) − 1)/(pᵢ − 1), φ(n) = ∏ pᵢ^(eᵢ−1)(pᵢ − 1)
CalculateTrial division by small primes
divide out each prime p while p × p ≤ remaining number
Divide by 59: 3599 ÷ 59 = 61
Remaining number: 61
CalculateTest the remaining number for primality
Miller–Rabin test
61 is prime (the Miller–Rabin test with the first 13 prime bases is a proof for numbers of this size).
ResultPrime factorization
3599 = 59 × 61
3599 is composite.
CalculateNumber of divisors τ(n) and sum of divisors σ(n)
τ(n) = (e₁+1)(e₂+1)…(eₖ+1), σ(n) = ∏ (p^(e+1) − 1) / (p − 1)
τ = (1+1) × (1+1) = 4
σ = (59^2 − 1)/(59 − 1) × (61^2 − 1)/(61 − 1) = 3720
Euler totient φ(n) = 58 × 60 = 3480
NoteAll 4 positive divisors
1, 59, 61, 3599
CheckVerify by multiplying back
59 × 61 = 3599 ✓ equals n
1 000 000 007 (prime)
Prime factorization
1000000007
Divisors τ(n)
2
sum of divisors σ(n) = 1000000008, φ(n) = 1000000006
1000000007 is prime: its only divisors are 1 and itself, φ(n) = n − 1.
Step-by-step solution
Formula used
n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ (unique, by the Fundamental Theorem of Arithmetic)
τ(n) = ∏(eᵢ + 1), σ(n) = ∏ (pᵢ^(eᵢ+1) − 1)/(pᵢ − 1), φ(n) = ∏ pᵢ^(eᵢ−1)(pᵢ − 1)
CalculateTrial division by small primes
divide out each prime p while p × p ≤ remaining number
No prime below 1000 (up to the square root) divides 1000000007.
Remaining number: 1000000007
CalculateTest the remaining number for primality
Miller–Rabin test
1000000007 is prime (the Miller–Rabin test with the first 13 prime bases is a proof for numbers of this size).
ResultPrime factorization
1000000007 = 1000000007
1000000007 is a prime number.
CalculateNumber of divisors τ(n) and sum of divisors σ(n)
τ(n) = (e₁+1)(e₂+1)…(eₖ+1), σ(n) = ∏ (p^(e+1) − 1) / (p − 1)
τ = (1+1) = 2
σ = (1000000007^2 − 1)/(1000000007 − 1) = 1000000008
Euler totient φ(n) = 1000000006 = 1000000006
NoteAll 2 positive divisors
1, 1000000007
CheckVerify by multiplying back
1000000007 = 1000000007 ✓ equals n
600851475143
Prime factorization
71 × 839 × 1471 × 6857
Divisors τ(n)
16
sum of divisors σ(n) = 610544148480, φ(n) = 591194251200
Step-by-step solution
Formula used
n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ (unique, by the Fundamental Theorem of Arithmetic)
τ(n) = ∏(eᵢ + 1), σ(n) = ∏ (pᵢ^(eᵢ+1) − 1)/(pᵢ − 1), φ(n) = ∏ pᵢ^(eᵢ−1)(pᵢ − 1)
CalculateTrial division by small primes
divide out each prime p while p × p ≤ remaining number
Divide by 71: 600851475143 ÷ 71 = 8462696833
Divide by 839: 8462696833 ÷ 839 = 10086647
Remaining number: 10086647
CalculateSplit the large remaining number
Pollard's rho algorithm with Miller–Rabin primality tests
10086647 has no factor below 1000, so a probabilistic splitting method (Pollard's rho) finds the remaining factors:
10086647 = 1471 × 6857
ResultPrime factorization
600851475143 = 71 × 839 × 1471 × 6857
600851475143 is composite.
CalculateNumber of divisors τ(n) and sum of divisors σ(n)
τ(n) = (e₁+1)(e₂+1)…(eₖ+1), σ(n) = ∏ (p^(e+1) − 1) / (p − 1)
τ = (1+1) × (1+1) × (1+1) × (1+1) = 16
σ = (71^2 − 1)/(71 − 1) × (839^2 − 1)/(839 − 1) × (1471^2 − 1)/(1471 − 1) × (6857^2 − 1)/(6857 − 1) = 610544148480
Euler totient φ(n) = 70 × 838 × 1470 × 6856 = 591194251200
NoteAll 16 positive divisors
1, 71, 839, 1471, 6857, 59569, 104441, 486847, 1234169, 5753023, 10086647, 87625999, 408464633, 716151937, 8462696833, 600851475143
CheckVerify by multiplying back
71 × 839 × 1471 × 6857 = 600851475143 ✓ equals n
Frequently asked questions
Is 1 a prime number?
No. A prime has exactly two positive divisors, but 1 has only one. Excluding 1 is what makes prime factorization unique.
How large a number can I factor?
You can enter up to 30 digits. Numbers with small or medium-sized prime factors are factored almost instantly; a number that is the product of two large primes may be reported as too hard to factor in the browser.
How do I find the number of divisors of a number?
Factor it as p₁^e₁ … pₖ^eₖ and multiply (e₁ + 1)(e₂ + 1)…(eₖ + 1). For 360 = 2³ · 3² · 5 that is 4 · 3 · 2 = 24 divisors.
What is the difference between a prime and a coprime pair?
A prime is a single number with no divisors besides 1 and itself. Two numbers are coprime when their greatest common divisor is 1, even if neither is prime, as with 8 and 15.