Prime Factorisation
Break a whole number into its prime factors, list its divisors and check whether it is prime.
Runs entirely in your browser. Nothing is uploaded, logged or stored.
Prime factorisation
2^3 × 3^2 × 5
- Is it prime?
- no
- Distinct prime factors
- 3
- How many divisors
- 24
- 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
Every whole number above 1 is a product of primes, and there is only one such product for it — that is the fundamental theorem of arithmetic. This finds it, and everything that follows from it: how many divisors the number has, and what they are.
How it works
Trial division, with one shortcut: after 2 and 3 are taken out, every remaining prime is one either side of a multiple of six, so the candidates step in sixes instead of in twos. Whatever survives the sieve is itself prime and goes in as the last factor.
The divisors are built from the factorisation rather than by testing every number up to n. A number written as 2³ × 3² × 5 has (3+1) × (2+1) × (1+1) = 24 divisors, and each is a choice of how many of each prime to take — so listing them costs nothing once the factorisation is known.
The ceiling is a thousand billion. Trial division touches at most the square root of the number, which is a million steps there — fast. Above it, a number that happens to be the product of two large primes would leave the page loading for a minute, so it refuses instead.
Examples
| Case | Input | Result |
|---|---|---|
| A highly divisible number | 360 | 2³ × 3² × 5 — 24 divisors |
| A prime | 97 | 97 — prime, 2 divisors |
| A power of two | 1024 | 2¹⁰ — 11 divisors |
Frequently asked questions
Why does it start at 2 rather than at 1?
Because 1 has no prime factorisation, and calling it prime would break the uniqueness the whole subject rests on: if 1 were prime then 6 would be 2 × 3, and 1 × 2 × 3, and 1 × 1 × 2 × 3, and there would no longer be one answer. Zero is worse still — every number divides it.
How many divisors does a number have?
Add one to each exponent in the factorisation and multiply. 360 is 2³ × 3² × 5, so 4 × 3 × 2 = 24. A prime has 2 — itself and 1 — and a perfect square always has an odd number of them, because one divisor is its own partner.
Why is there a ceiling?
Trial division is exact and fast until it is not. The worst case is a product of two primes near the square root, and the limit here is where that case still returns inside a page load. A refusal tells you what happened; a timeout tells you nothing.
Is this how encryption keys are broken?
No, and that is rather the point. RSA rests on the difficulty of factorising a number a few hundred digits long; trial division on one of those would outlast the universe. The methods that do better exist and are still nowhere near enough, which is why the scheme works.
Good to know
- Divisors are listed in full up to sixty-four of them; beyond that only the count is shown, because a page of nine hundred numbers is not something anybody reads.