Prime Factorisation Calculator
Enter a whole number to get its prime factors in index form, whether it is prime, how many divisors it has and every one of them. Any number up to one quadrillion (10¹⁵) is split instantly.
- Prime?No, composite
- Prime factors (with repeats)6
- Distinct prime factors3
- Number of divisors24
- Sum of divisors σ(n)1,170
- Euler’s totient φ(n)96
Step-by-step division
How it is calculated
By the fundamental theorem of arithmetic, every whole number above 1 is a product of primes in exactly one way. That factorisation makes GCDs, LCMs, simplifying fractions and simplifying square roots easy. The difficulty of factoring huge numbers is also what keeps encryption such as RSA safe.
n = p₁^e₁ × p₂^e₂ × … · Number of divisors = (e₁ + 1)(e₂ + 1)…p: the prime factors (smallest first) · e: the power of each. Sum of divisors σ(n) = Π (1 + p + … + pᵉ), Euler’s φ(n) = Π pᵉ⁻¹(p − 1).- Divide by 2 as long as it goes, then by 3, 5, 7 …; each successful division gives a prime factor.
- Stop when the trial divisor passes the square root: anything above 1 that is left is prime too.
- For very large numbers, after trial division up to 100,000 the rest is settled by the Miller–Rabin test and Pollard’s rho method; the result is still exact: Miller–Rabin with the first 12 primes as bases is conclusive for every number below about 3.19 × 10²³ (Sorenson and Webster 2017).
- Equal factors are collected as powers: 2 × 2 × 2 = 2³.
Example
360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. So 360 = 2³ × 3² × 5. It has (3 + 1)(2 + 1)(1 + 1) = 24 divisors, which add up to 15 × 13 × 6 = 1,170.
Frequently asked questions
Is 1 a prime number?
No. A prime has exactly two divisors, 1 and itself; 1 has only one. It is neither prime nor composite. The smallest prime is 2, the only even one.
How can I tell whether a number is prime?
It is prime if no prime up to its square root divides it. For 97, √97 ≈ 9.8, and 2, 3, 5 and 7 do not divide it, so 97 is prime.
How is the number of divisors found?
Add one to each power in the index form and multiply. For 360 = 2³ × 3² × 5¹ that is (3 + 1) × (2 + 1) × (1 + 1) = 24 divisors. Choose “Divisors” to list them all in pairs.
Can negative numbers or 0 be factorised?
Factorisation is defined for positive whole numbers. A negative number is −1 times its positive counterpart (−360 = −1 × 2³ × 3² × 5); 0 is divisible by everything, so it has no factorisation.
Source
- Sorenson, J. and Webster, J. (2017). Strong pseudoprimes to twelve prime bases. Mathematics of Computation 86, 985–1003
- OEIS A014233 — smallest odd composite strong pseudoprime to the first n prime bases
- Pollard, J. M. (1975). A Monte Carlo method for factorization. BIT 15, 331–334
- Rivest, Shamir and Adleman (1978). A method for obtaining digital signatures and public-key cryptosystems. CACM 21(2)
- OEIS A000040 — the prime numbers
- NIST DLMF §27.2 — primes and arithmetic functions