Prime factorization calculator

What is prime factorization?

Every whole number above one is either prime — divisible only by itself and one — or a product of primes, and that product is unique apart from the order you write it in. That is the fundamental theorem of arithmetic, and prime factorization is the act of finding it: 360 is 2 × 2 × 2 × 3 × 3 × 5, usually written 2³ × 3² × 5, and no other combination of primes multiplies to 360.

It is the operation underneath a good deal of ordinary arithmetic. Reducing a fraction means cancelling shared prime factors. A lowest common denominator is built from the primes of each denominator, taking the highest power of each. The number of divisors a number has falls straight out of its factorization: multiply each exponent plus one together, so 360 = 2³ × 3² × 5¹ has 4 × 3 × 2 = 24 divisors, and the tool lists all of them.

This calculator works in exact integer arithmetic rather than floating point, so there is no size at which the answers quietly become approximate. Paste a forty-digit number and every factor it reports is exactly right.

How to use it

1. Type or paste a whole number. Commas, spaces and underscores are ignored, so a number copied out of a spreadsheet works as it stands. Decimals, minus signs and exponent notation are rejected rather than silently reinterpreted.
2. Read the factorization and the divisors. Composite numbers appear in exponent form with every prime factor listed, plus a divisor count and, when the list is a reasonable length, every divisor. A prime number is simply reported as prime.
3. If it says it did not finish, believe it. Hard numbers hit a work limit and the tool tells you so, showing what it did find and what is left. The button offers a longer search; if that fails too, the number is genuinely beyond what a browser can do in a reasonable time.

Why some numbers stop it, and why that is the point

Factoring is enormously easier for some numbers than others, and the gap is not about size. Dividing out small primes handles most numbers instantly, because most numbers have a small factor — over forty random forty-digit numbers, the middling one factors in about a sixth of a second. What is hard is a number with no small factors at all: a semiprime, the product of two large primes and nothing else.

The naive method makes this vivid. Trial division tries every candidate up to the square root, so its cost doubles roughly every two digits: on the machine this page was built on, a semiprime of two ten-digit primes took three seconds and one of two eleven-digit primes took three and a half minutes. This tool uses Pollard's rho instead, which took that same eleven-digit case from 212 seconds to 68 milliseconds — a difference of three orders of magnitude, from an algorithm that fits in twenty lines.

But rho only moves the wall; it does not remove it. A semiprime of two thirteen-digit primes is still out of reach in a browser tab, and that is not a shortcoming to apologise for. It is the whole basis of public-key cryptography: RSA keys are semiprimes chosen precisely because multiplying two large primes is trivial and undoing it is not. The numbers guarding your bank are the same shape as the one this page gives up on, only vastly larger.

That is why the limit here is a work budget rather than a digit cap. A digit cap would be wrong in both directions — it would refuse the forty-digit number that factors in a millisecond and accept the twenty-five-digit one that takes seconds. Counting effort instead means the tool stops when the work becomes unreasonable, whatever the number looks like, and reports honestly rather than freezing the tab.

Honest limits

When the search stops early, everything shown is still true. The factors it found really are prime factors of your number; what remains is simply not broken down. Multiply the reported factors by the leftover and you get your number back exactly — that property holds at every budget, and is the thing the tests check hardest, because a partial answer that quietly claims to be complete is far worse than one that admits it stopped.

Primality is decided by the Miller-Rabin test with a fixed set of twelve witnesses. That combination is proven correct for every number below about 3.3 × 10²⁴, which covers everything this tool will realistically be handed; above that it becomes a probabilistic test rather than a proof, and the chance of error is vanishingly small but not zero. Most calculators do not mention which side of that line they are on.

Zero and one get their own answers rather than an empty result. Zero has no factorization, since every number divides it. One is neither prime nor composite — it has no prime factors at all, which is a fact about the definition rather than an oversight, and the reason the fundamental theorem starts at two.

The divisor list is capped in the display, because a highly composite number can have thousands and rendering them all helps nobody. The count above it is always the true total, computed from the exponents rather than by counting what is shown.

Why is it free?

Because it costs nothing to run. All the arithmetic happens in your browser using its built-in big-integer support — nothing is uploaded, no server sees your numbers, and there is no account or limit on how many you check.

The engine is checked against an independently written factoriser in another language, and against something stronger than any reference implementation: a factorization can be verified by multiplying it back, and the tests do that at every work budget down to zero. Two of the bugs that check caught were exactly the dangerous kind — a partial answer presented as complete, and a leftover factor reported as prime.