Prime Number Calculator: Factorization and Divisors
Enter a whole number to find out whether it's prime, get its prime factorization, and the list of its divisors. A prime number has only two divisors — 1 and itself — so its factorization comes out as a single factor, raised to the power of one.
Calculator
Results
| Is — prime? | — |
| Prime factorization | — |
| Number of positive divisors | — |
| Sum of divisors | — |
| List of divisors | — |
How a prime factorization is calculated
Trial division by 2, 3, 5, 7… up to √n: each divisor found is a prime factor
Number of divisors = product of (exponent + 1) for each prime factor
It's enough to test divisors up to the square root of n: if no prime factor at or below √n divides n, then n is prime — any divisor beyond that would have a smaller "partner" already tested. The total number of divisors follows directly from the exponents of the factorization, without having to list them all.
A star after a term points to the glossary below.
Prime versus composite: the two-divisor definition
A whole number greater than 1 is prime* when its only positive divisors are 1 and itself. It cannot be written as a product of two smaller whole numbers.
The first few are 2, 3, 5, 7, 11, 13, 17, 19, 23 — the list most classrooms meet in year 7. 4 is out (2 × 2), so is 9 (3 × 3), so is 15 (3 × 5). Those are composite*. From 2 upwards there is no third shelf: a number is prime, or it factors.
This calculator reads the answer off the factorisation. One prime, raised to the first power: prime. Two primes, or a square, or anything lumpier: composite. 9 = 3² is not prime. A single prime in the display is not enough if the exponent is greater than 1. GCSE language is “product of primes”; an SAT item says “prime factorization”. Same list of factors.
Why 1 is left off the list
Every year the question comes back. 1 is only divisible by 1, so why the fuss?
The definition wants two distinct positive divisors. 1 has one. It is not composite either: it does not split into smaller whole numbers. It sits on its own. The serious reason is unique factorisation. Every integer > 1 is a product of primes in only one way, up to order. Let 1 count as a prime and any factorisation can be padded with as many ones as anyone likes (1 × 1 × 5 = 5). Uniqueness collapses. So 1 is left out. It is not a textbook whim.
The form will not take anything below 2. There is simply nothing to factor.
Trial division up to the square root
To decide whether n is prime, it is enough to test whole divisors up to √n. If no prime factor at or below √n divides n, then n is prime. Any larger divisor would have a smaller partner already tested.
Trial division by 2, 3, 5, 7… up to √n: each divisor found is a prime factor
That is trial division*. For 360 the search starts at 2 (it divides, repeatedly), then 3 (likewise), then 5, and stops: 360 = 2³ × 3² × 5. For 97, nothing up to √97 ≈ 9.8 divides, so 97 is prime. √1,000,000,000 is about 31,623 trials. A PHP loop of that length finishes before the page renders.
Past a few dozen digits the same method is hopeless. √n then has half as many digits as n, and 1025 divisions are not a waiting time anyone accepts. At that size the job splits: a primality test (Miller–Rabin in practice) can certify “prime” without producing a single factor. Factoring is a different, harder problem. RSA is betting that it stays hard.
The sieve of Eratosthenes, when a whole table is wanted
Trial division up to √n is the right test for one candidate. For every prime up to a bound N, the sieve of Eratosthenes* is the older, cheaper sweep.
- Write the integers from 2 to N.
- 2 is prime: strike its multiples (4, 6, 8…).
- The next unmarked number, 3, is prime: strike 6, 9, 12…
- Carry on with 5, 7 and so on, as far as √N. Whatever is still unmarked is prime.
The range is swept, not probed one integer at a time. Each composite is visited only a handful of times, which is why a sieve fills a table of primes into the millions without drama. This page does not do that. It answers for a single n. Generating the fifty million primes below a billion to decide about 360 would be theatre, not arithmetic.
Unique factorisation and the count of divisors
The fundamental theorem of arithmetic says every integer greater than 1 factors into primes in only one way, up to order. 360 is always 2³ × 3² × 5, never 2² × 90 with 90 left composite. Once the exponents sit on the page, the number of positive divisors is a product, not a hunt.
Number of divisors = product of (exponent + 1) for each prime factor
For 360: (3+1)×(2+1)×(1+1) = 4×3×2 = 24 divisors. The sum of those divisors is another product, built from geometric series: (2⁴−1)/(2−1) × (3³−1)/(3−1) × (5²−1)/(5−1). No need to list 1, 2, 3, 4, 5, 6, 8, 9… unless the list itself is wanted. This page lists them when there are at most 300; past that it prints the count and hides the row.
Highly composite inputs (many small prime factors) produce long lists. A prime produces the shortest list of all: 1 and itself.
Perfect numbers and the sum of divisors
A number is perfect* when its proper divisors — every divisor except the number itself — add back up to it.
6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. Next come 496 and 8,128. The sequence thins out fast. Every even perfect number has the shape 2p−1(2p − 1) once 2p − 1 is a Mersenne prime (Euclid–Euler). Nobody has found an odd perfect number. Nobody has proved there is not one. Both questions — odd perfects, infinitely many even ones — remain open, which has not stopped 6 and 28 from appearing in every textbook.
The table here sums all divisors, n included. A perfect number therefore shows a divisor-sum of 2n. For 28, look for 56. Abundant numbers overshoot 2n; deficient numbers fall short. 12 is abundant (sum 28); 8 is deficient (sum 15).
Twin primes and Mersenne primes
Twin primes differ by 2: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31). Staggeringly large pairs are known. Whether infinitely many exist remains open.
A Mersenne* number is 2p − 1. For that to be prime, p itself must be prime — necessary, not enough. 211 − 1 = 2,047 = 23 × 89, and 11 is prime. Why bother with the shape? Almost every “largest known prime” is a Mersenne prime. It admits a specialist test (Lucas–Lehmer) that leaves trial division in the dust. GIMPS, a volunteer network, has been hunting these records since the 1990s. This calculator will not join the hunt. 219 − 1 fits under a billion; 231 − 1 does not.
Twins and Mersenne numbers are curiosities the form can poke. They are not a special mode of the arithmetic.
Euclid's proof that the primes never run out
Euclid shows there are infinitely many primes without handing over a formula for the next one.
Suppose only finitely many existed: p1, p2, …, pk. Form N = p1 × p2 × … × pk + 1. None of the pi divide N (the remainder is 1). So either N is itself prime — missing from the list — or it has a brand-new prime factor. Either way the list was incomplete. Repeat. The next prime is not constructed. Another one is always waiting.
N = (product of the supposed primes) + 1 → a new prime, or a new factor
They do get scarcer. Between 1 and 100 there are 25 primes; between 1 and 1,000 there are 168. Rarer is not the same as last. The gaps grow, on average, like the logarithm of n — the prime number theorem, centuries after Euclid, and well outside this page.
Why a billion is the ceiling here
Trial division is instant, and the divisor list fits on the screen — except for a few highly composite inputs, whose list is then hidden (more than 300 divisors).
Go larger and a modern machine does not immediately fall over. The teaching value does. Nobody checks a twelve-digit number by hand, and the jobs that actually need huge primes — keys, records — live at sizes where trial division has no business. A billion is an honest ceiling: big enough for school, an ID, a contest problem; small enough that this box cannot be mistaken for a key-breaking tool. √n tops out near 31,000, which is a PHP loop the page can finish before it renders.
A bigger integer is a different tool. And a different problem.
Two is the only even prime
Every even integer other than 2 is divisible by 2, hence composite. Two stands alone.
It sounds like a schoolyard joke, and it shortens a lot of arguments. Past 2, the hunt is among the odd numbers. A sieve's first pass already blanks every other cell: parity is the coarsest filter there is. Twin primes, for their part, are almost always two odds two apart. The pair (2, 3) is adjacent, not twin.
If a number ends in 0, 2, 4, 6 or 8 and it is not 2, it is not prime. The last digit is enough. The same glance is a divisibility test for 2, used here as a first cut rather than as a full table of remainders.
RSA, and why this page is not a key-breaking tool
In a classroom, primes are factored. On a server they hide information.
Public-key cryptography — RSA is the name people actually use — multiplies two enormous primes, n = p × q. Forming the product is cheap. Recovering p and q from n, without being given them, is out of reach once those primes run to a few hundred digits. That is the public key: n can sit in the open; the factors cannot. Primes also turn up as hash-table sizes (a prime modulus spreads collisions), in some pseudo-random generators, in error-correcting codes. Same underlying habit: arithmetic modulo a prime is well-behaved; a product of two large primes is a nuisance to take apart.
Nothing on this page is a cryptographic prime. The cap is one billion — ten digits, GCSE territory. A typical RSA modulus is 2,048 bits, over 600 digits. Factoring 360 will not teach anyone how to break a key.
Goldbach's conjecture
Every even integer greater than 2 would be a sum of two primes. 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 3+7 = 5+5, and so on.
Computers have checked it out to vast bounds. Nobody has proved it. It is a conjecture, not a theorem — worth saying out loud, even though the claim fits in one sentence and no counter-example has ever turned up. A weaker form (every odd integer ≥ 7 is a sum of three primes) has been proved. The strong form, the one that turns up in popular maths, remains unproved. The statement is shorter than any honest account of why the proof is stuck.
This page does not test Goldbach. It factors one integer. An even number can be split by hand, and two primes that add back to it can be hunted for fun. That is not a proof.
Factorisation versus Euclid, when a fraction needs cancelling
Cancelling a fraction means stripping the factors the numerator and the denominator share. Those shared factors are the GCD*.
If a = 2³ × 3² × 5 and b = 2² × 3 × 7, the GCD takes the smaller exponent of each prime: 2² × 3 = 12. The LCM takes the larger: 2³ × 3² × 5 × 7 = 2,520. 360/12 over 84/12 is the cancelled fraction 30/7. Euclid's algorithm is unnecessary once both factorisations sit in front of the eye — provided the numbers are small enough to factor in the first place. Same ingredients, two jobs: split one integer, or compare several.
The GCD and LCM calculator works the other way round, with Euclid's algorithm, and it accepts a whole list. The fraction calculator then prints the reduced result. The two pages, plus this one, cover the same arithmetic from three angles.
Glossary
- Prime number
- A whole number greater than 1 whose only positive divisors are 1 and itself. The first few: 2, 3, 5, 7, 11. Two is the only even prime.
- Composite number
- A whole number greater than 1 that is not prime: it factors as a product of smaller whole numbers. 4, 9, 15, 360 are composite. 1 is neither prime nor composite.
- Trial division
- Testing successive whole divisors up to √n. If none divide n, n is prime; each divisor that does divide is a prime factor. Honest up to about a billion; hopeless for cryptographic sizes.
- Sieve of Eratosthenes
- A method for listing every prime up to a bound N: write 2 through N, then strike multiples of each remaining number as far as √N. What is left unmarked is prime.
- Perfect number
- A number equal to the sum of its proper divisors (every divisor except itself). 6, 28, 496, 8,128. Even perfect numbers come from Mersenne primes; no odd perfect number is known.
- Mersenne prime
- A prime of the form 2p − 1, which requires p itself to be prime (necessary, not sufficient). Almost every record-size prime is of this shape, because a specialised test (Lucas–Lehmer) applies.
- GCD
- Greatest common divisor of two or more integers: the largest positive integer that divides all of them. Read off the smaller exponents once both prime factorisations are known, or computed by Euclid's algorithm without factoring.