How to Find the Prime Factorization of a Number

Prime factorization is writing a number as a product of prime numbers, the smallest building blocks that multiply back up to it. Every whole number greater than 1 breaks down into exactly one such combination (that’s the fundamental theorem of arithmetic), which is why it’s useful: once you have the primes, you have everything about a number’s divisibility in one compact form. Simplifying fractions, finding a GCD or LCM, checking whether a number is prime, and even the math behind RSA encryption all come back to this same operation.

Trial division by hand

The method that works for any number, prime or composite, small or large, is trial division: divide repeatedly by the smallest prime that fits, and keep going with the quotient until you’re left with 1.

Start with 2. If the number is even, divide by 2 and repeat with the result, still checking 2 first, until it stops being even. Then move to 3, then 5, then 7, and so on through the primes, dividing as many times as each one goes in before moving to the next.

Here’s 360 worked all the way through:

Step	Divide by	Result
360	2	180
180	2	90
90	2	45
45	3	15
15	3	5
5	5	1

Three divisions by 2, then two by 3, then one by 5, and you hit 1. Collect the divisors used: 2, 2, 2, 3, 3, 5. Written with exponents to group the repeats, that’s 360 = 2³ × 3² × 5. Multiply it back out as a check: 8 × 9 × 5 = 72 × 5 = 360. It matches, which is the habit worth keeping every time you do this by hand.

Note the order the primes came out in, three 2s before any 3s, then the 3s before the 5. That’s not a coincidence of this example, dividing by the smallest available prime first is what keeps the process simple and guarantees you don’t miss a factor along the way.

A bigger example, and how to check if a number is prime

Trial division scales fine to bigger numbers, it just takes more steps. Take 2,310:

Step	Divide by	Result
2310	2	1155
1155	3	385
385	5	77
77	7	11
11	11	1

This one is different from 360 in a telling way: each prime divides in exactly once. 2,310 = 2 × 3 × 5 × 7 × 11, five distinct primes with no repeats (it’s the product of the first five primes, sometimes called a primorial). Same method, different shape of answer.

Now a genuinely useful related question: is 997 prime? You don’t need to test every number smaller than 997 as a possible divisor. You only need to test primes up to the square root of 997, which is about 31.6. Here’s why that limit works: if 997 had a divisor larger than its square root, it would have to pair with a divisor smaller than the square root to multiply back to 997, and you’d have already found that smaller one. So once your trial divisor squared exceeds the number you’re testing, you can stop, whatever’s left over is prime.

Testing 997 against every prime up to 31: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. It’s odd, so 2 is out. Its digits sum to 25, not divisible by 3. It doesn’t end in 0 or 5, so 5 is out. Dividing by 7 gives 142 remainder 3. By 11, 90 remainder 7. By 13, 76 remainder 9. By 17, 58 remainder 11. By 19, 52 remainder 9. By 23, 43 remainder 8. By 29, 34 remainder 11. By 31, 32 remainder 5. Nothing divides evenly, and 31 is the last prime to check since 37² is already 1,369, well past 997. So 997 is prime.

Calculate with your own numbers

Working through the steps by hand is worth doing once or twice so the method sticks, but for anything bigger than a few digits, or when you just need the answer, use the calculator below. It runs the same trial-division logic and shows the exponent form, the full divisor list, and a prime/composite check instantly.

Prime Factorization Calculator

Free, no sign-up, works on any device.

Open the full tool

Real-world uses: simplifying fractions and counting divisors

Simplifying a fraction by canceling shared primes

Take 84/126. Factor both: 84 = 2² × 3 × 7, and 126 = 2 × 3² × 7. Line them up and take the lowest power of every prime they share: 2¹ × 3¹ × 7¹ = 42, the greatest common divisor. Divide numerator and denominator by 42: 84/42 = 2, and 126/42 = 3. So 84/126 reduces to 2/3, and you got there without any guesswork about what number might divide both, the primes told you exactly.

This is the same move behind reducing any fraction, matching units in a ratio, or simplifying a square root: break both numbers into primes, cancel what overlaps, and whatever’s left is already in lowest terms.

Counting and listing every divisor

Once you have the exponents, the total number of divisors falls out of a short formula: add 1 to each exponent and multiply the results together. For 360 = 2³ × 3² × 5¹, that’s (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 divisors. You can list all 24 by combining every choice of exponent for 2 (0 through 3), 3 (0 through 2), and 5 (0 or 1):

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360

That’s exactly 24 numbers, and every one of them divides 360 with nothing left over. This matters beyond curiosity: it’s how you find every way to arrange 360 objects into equal rows and columns, every possible even split of a schedule that repeats every 360 units, or every whole-number factor pair for a design that needs to tile evenly.

Prime factorization also sits underneath modern cryptography, in a rougher but related way. RSA encryption relies on multiplying two very large primes together to get a number that’s trivial to compute forward but currently infeasible to factor back apart, even with serious computing power, once those primes run into the hundreds of digits. The gap between “easy to multiply” and “hard to un-multiply” at that scale is the entire security guarantee.

Here’s how the first several integers break down, useful as a quick reference for the pattern:

n	Factorization	Prime?	Divisor count
2	2	Yes	2
3	3	Yes	2
4	2²	No	3
5	5	Yes	2
6	2 × 3	No	4
7	7	Yes	2
8	2³	No	4
9	3²	No	3
10	2 × 5	No	4
12	2² × 3	No	6
16	2⁴	No	5
18	2 × 3²	No	6
20	2² × 5	No	6

Notice that every prime has exactly 2 divisors (1 and itself), and that the divisor count only climbs when a number has several distinct prime factors or high exponents, not just because the number itself is large. 16 is bigger than 12 but has fewer divisors, because it’s built from a single repeated prime instead of a spread of different ones.

Common mistakes and edge cases

Treating 0 or 1 as prime or composite. Neither one is either. 1 has only one divisor (itself), and primes are defined as having exactly two, so 1 fails that test on the low end. 0 is divisible by every integer, which breaks the “exactly two divisors” definition from the other direction, and it has no prime factorization at all.

Forgetting to divide by the same prime more than once. If you check 2, find it divides once, and move straight to 3 without checking whether 2 still divides the new quotient, you’ll miss factors. Always keep dividing by the current prime until it stops working before moving to the next one, that’s how 360 ends up with three 2s instead of one.

Ignoring the sign on a negative number. Prime factorization applies to the absolute value. -360 has the same prime factors as 360, the negative sign isn’t part of the factorization itself.

Not knowing when to stop. You don’t need to test every number up to n minus 1, or even up to n divided by 2. Once your trial divisor’s square exceeds whatever’s left of the original number, stop, the remainder is prime on its own. That’s what made checking 997 fast: only eleven primes to test, not 995.

FAQ

What is prime factorization used for? It underlies simplifying fractions and radicals, finding a greatest common divisor or least common multiple, determining the total number of divisors a number has, and (at a much larger scale, with hundreds-of-digit primes) the security behind RSA public-key encryption. Any problem about how a number divides evenly usually reduces to looking at its prime factors.

How do I know if a number is prime just by looking at it? A few quick checks catch most composites instantly: even numbers past 2 are out, anything ending in 0 or 5 is divisible by 5 (except 5 itself), and if the digits sum to a multiple of 3 the number is divisible by 3. Beyond that there’s no shortcut that works by inspection alone, you need to trial-divide by primes up to the square root, as shown with 997 above.

What’s the largest number I can factor by hand reasonably? Trial division by hand stays practical up to somewhere around 4 to 6 digits, past that the number of primes you’d need to test up to the square root gets tedious even though the method never actually fails. The calculator on this page handles anything up to one trillion using the same trial-division approach, just a lot faster.

Are 0 and 1 prime or composite? Neither. Primality requires exactly two distinct divisors, 1 has only one divisor and 0 has infinitely many, so both fall outside the definition on opposite sides.

Why does every number have only one prime factorization? This is the fundamental theorem of arithmetic: for any whole number greater than 1, its prime factors and their exponents are unique, no matter what order you find them in or which method you use to get there. Two different valid factorizations of the same number would multiply out to different values, which isn’t possible, that uniqueness is exactly what makes prime factors a reliable fingerprint for a number’s divisibility.