Prime Factorization Calculator

What a prime number is

A prime is a whole number above 1 whose only positive divisors are 1 and itself. The list starts 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and it never ends. Every other whole number above 1 is composite, which means it breaks into smaller pieces. The number 1 counts as neither: it has only one divisor, and the definition asks for exactly two.

Spotting composites is a skill of looking at last digits and digit sums. Anything ending in 0, 2, 4, 5, 6 or 8 is divisible by 2 or 5. A number whose digits add to a multiple of 3 is divisible by 3. That catches 91? No: 91 passes those tests, yet 91 = 7 × 13. The tests are shortcuts, not proof. Only a run of failed divisions proves a number prime.

The On-Line Encyclopedia of Integer Sequences keeps the running list of primes as entry A000040 (accessed 2026), and it records one more fact worth knowing: 2 is the only even prime, because every other even number is divisible by 2 and therefore larger than 2 and composite. That single observation halves the work of any factoring routine, and the calculator on this page uses it.

Trial division stops at the square root

The oldest factoring method is trial division, and it comes with a built-in stopping rule. If n = a × b and a is the smaller factor, then a × a cannot exceed n, so a cannot exceed the square root of n. Put the other way: if you have divided by every candidate up to the square root of n and nothing went in evenly, n is prime.

Take 91. Its square root is about 9.54, so the only candidates are 2, 3, 5, 7 and 9. Two fails, three fails (9 + 1 is 10, not a multiple of 3), five fails, and then 91 ÷ 7 = 13. Found at the fourth try. Now take 101. Its square root is about 10.05, so candidates are 2, 3, 5 and 7, and none of them divides 101. That run of failures is the proof: 101 is prime.

The cutoff matters for cost. Checking divisors up to n instead of up to the square root of n squares the work. For a number near one trillion, the square root is one million, so a worst case run does about a million divisions, which a browser finishes in a blink. That is why the calculator on this page accepts inputs up to about 10 to the 12th: trial division stays fast all the way to that range, and past it the wait grows quickly.

Two full examples, one division at a time

Here is 360 factored by hand, writing down every division. Divide by 2 while it goes in evenly, then move to the next candidate, skipping the numbers that cannot be prime.

Collecting the winners: 360 = 2 × 2 × 2 × 3 × 3 × 5. The quotient hit 1, so nothing is left over. A second example, 9,240, runs the same way: 9,240 ÷ 2 = 4,620, then 4,620 ÷ 2 = 2,310, then 2,310 ÷ 2 = 1,155 (odd now), then 1,155 ÷ 3 = 385, then 385 ÷ 5 = 77, then 77 ÷ 7 = 11, and 11 ÷ 11 = 1. So 9,240 = 2 × 2 × 2 × 3 × 5 × 7 × 11. Two numbers, two different shapes: 360 repeats its primes three and two times over, while 9,240 carries five distinct primes.

Exponential form and the Fundamental Theorem of Arithmetic

Repeated factors are written as powers. Group the 2s and the 3s in 360 and you get the exponential form 360 = 2³ × 3² × 5, read as two cubed times three squared times five. The 5 stands alone because it appears once. In that notation 9,240 = 2³ × 3 × 5 × 7 × 11, and a prime such as 9,973 is its own factorization, a single unsplittable piece.

The guarantee behind all of this is the Fundamental Theorem of Arithmetic: every integer from 2 up factors into primes in exactly one way, apart from the order of the factors. The Emory University course notes on the theorem walk through the proof (accessed 2026). No matter how you hunt, 360 always comes back as three 2s, two 3s and one 5.

That uniqueness turns a factorization into a fingerprint. Two numbers are equal exactly when their prime fingerprints match, prime by prime and exponent by exponent. It also means the factoring algorithm needs no cleverness to be correct: as long as it divides out each smallest factor completely, the result cannot come out two ways. Conventions put the primes in increasing order and write exponents above 1 only, so 2³ × 3² × 5 is the canonical form of 360.

GCD and LCM straight from the exponents

Once two numbers sit in exponential form, their greatest common divisor and least common multiple fall out by inspection. For each prime, the GCD takes the smaller exponent and the LCM takes the larger. Missing primes count as exponent 0.

A quick check ties them together: GCD × LCM = 120 × 27,720 = 3,326,400, and 360 × 9,240 is the same product. That identity holds for any pair of positive integers.

Concretely, this is how you add fractions without a calculator. To add 5/360 and 7/9,240, work over the LCM 27,720: the fractions become 385/27,720 and 21/27,720, which sum to 406/27,720. The GCD of 406 and 27,720 is 2 × 7 = 14, and dividing top and bottom by 14 leaves 29/1,980. Exponent min and max did all the work.

Counting and summing all the divisors

The divisor count and divisor sum of n come straight from the exponents, with no listing of divisors at all. If n = p^a × q^b × ..., the count is (a + 1)(b + 1) × ..., because a divisor picks one power of each prime from 0 up to its exponent. The sum multiplies out one block per prime: 1 + p + ... + p^a for each.

For 360 = 2³ × 3² × 5: the count is (3 + 1)(2 + 1)(1 + 1) = 24. The sum is (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 × 13 × 6 = 1,170. You can add up the 24 divisors by hand and land on the same 1,170, which is a decent way to check the formula the first time.

The last row is the shortcut: a prime has exactly 2 divisors, namely 1 and itself, and its divisor sum is n + 1. If the formulas ever hand you a count of 2, the input was prime and you can stop there. A perfect square has an odd divisor count, as 100 does with 9, because one divisor, the square root, pairs with itself.

Factoring at work: reducing fractions and pulling out square roots

Two everyday jobs reduce to comparing prime exponents. The first is reducing a fraction. Take 84/126: since 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7, the shared part is 2 × 3 × 7 = 42, and dividing top and bottom by 42 gives 2/3. Same trick on 504/9,240: 504 = 2³ × 3² × 7 against 9,240 = 2³ × 3 × 5 × 7 × 11, the minimum exponents give 2³ × 3 × 7 = 168, and the fraction collapses to 3/55.

The second is simplifying a square root. Factor the number, then pair the primes: each pair of the same prime comes out of the root as one copy, and the unpaired leftovers stay inside. For the square root of 72 = 2³ × 3², the pair of 2s leaves one 2 under the root and one comes out, and the pair of 3s comes out whole: the answer is 2 × 3 × the square root of 2, or 6 times the square root of 2. Try 504 = 2³ × 3² × 7: out come 2 and 3, inside stays 2 × 7, so the simplified form is 6 times the square root of 14.

Both jobs are the same move as GCD and LCM, just dressed differently: minimum exponents cancel a fraction, and pairs of exponents decide what escapes a radical.

Why big-number factoring is hard, and what RSA counts on

Everything above scales fine to a trillion. Past that, factoring turns from a chore into a wall, and modern cryptography is built on the wall. An RSA key starts with a modulus n that is the product of two large primes, and anyone can multiply those primes; the security rests on the reverse trip being far slower. NIST FIPS 186-5 (2023), the US Digital Signature Standard, requires an RSA modulus with an even bit length of at least 2,048 bits, built from two primes of equal bit length.

Some honest arithmetic shows why. A 2,048-bit modulus is a number with about 617 decimal digits, since 2^2,048 is roughly 10^616.5. Trial division would need around the square root of that, near 10³⁰⁸ divisions, which no schedule of computers finishes. The best known classical methods improve on trial division by a wide margin, but they still slow down sharply as digits are added, and no fast classical factoring method is known. Multiplying two 300-digit primes takes microseconds; recovering them from the product resists the entire combined effort of the field.

One caveat belongs in any current telling: a large enough quantum computer running Shor's algorithm would factor such moduli, which is why NIST published post-quantum signature and encryption standards in 2024 and agencies have begun migrating. For classical hardware, though, the one-way street holds, and the difficulty of the trip backward is exactly what your browser's secure connection leans on.