Prime Factorization Calculator

What is a prime number?

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. 7 is prime, because the only whole numbers that multiply to give it are 1 and 7. The same is true of 2, 3, 5, 11 and infinitely many others.

Numbers that can be formed from two smaller natural numbers greater than 1 are composite. 4, 6 and 9 are all composite, since they are 2 × 2, 2 × 3 and 3 × 3.

1 belongs to neither group. It is not prime and it is not composite, which is a definition rather than an oversight: allowing 1 to be prime would break the uniqueness described below, since 6 could then be written as 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3, without end.

Primes matter in number theory because of the fundamental theorem of arithmetic, which says every natural number above 1 is either prime or can be written as a product of primes. The number 60, for instance:

60 = 5 × 3 × 2 × 2

There are no composite numbers anywhere in that factorization, and there is only one such list for 60. Reordering the terms does not count as a different factorization, so the decomposition is unique.

What is prime factorization?

Prime factorization is the decomposition of a composite number into a product of prime numbers. Several algorithms exist and some are considerably more involved than others. Two are worth knowing by hand.

Trial division

Trial division is among the most basic methods, and it is tedious in exactly the way its name suggests. Test each integer in turn by dividing the composite number by it, checking whether it divides evenly and how many times. Here is 820 done that way:

820 ÷ 2 = 410
410 ÷ 2 = 205

205 is no longer divisible by 2, so move to the next integers. 205 cannot be divided evenly by 3. 4 is not prime and can be skipped. It does divide by 5:

205 ÷ 5 = 41

41 is prime, which concludes the division. So:

820 = 41 × 5 × 2 × 2

The repeated factors can be gathered into exponents:

820 = 41 × 5 × 2²

This is essentially the brute-force approach. 820 is a gentle example, and the work grows uncomfortable very quickly.

Two shortcuts make it bearable. Only primes need testing, since any composite divisor is built from primes that were tried earlier. And testing can stop once the trial divisor exceeds the square root of what remains, because a factor above the square root would have to pair with one below it, which would already have been found. That is why the calculator stops at 41 for 820 rather than grinding on to 205.

Prime decomposition with a factor tree

The other common approach is prime decomposition, usually drawn as a factor tree. Break the composite number into two factors, then keep breaking any factor that is not yet prime. Below, 820 is split by the prime 2, and the result is divided again until every branch ends on a prime:

The two trees take different routes and arrive at the same place:

820 = 41 × 5 × 2 × 2

That is the fundamental theorem of arithmetic again. It does not matter which factor you happen to spot first, or whether you start with a prime or a composite; the collection of primes at the bottom is always the same. The calculator on this page draws the left-hand style, taking out the smallest prime available at each step, which keeps the tree narrow and predictable.

Why large numbers are hard

These methods work comfortably for small numbers, and many other algorithms exist, but no known method factors much larger numbers quickly. Even substantial machines can take a very long time. In 2009 a team finished a project using hundreds of machines to factor RSA-768, a 232-digit number, and it took roughly two years.

That difficulty is not an inconvenience; it is the foundation of RSA encryption. Multiplying two large primes is instant, while recovering them from the product is not, and the gap between those two costs is what protects a great deal of internet traffic. Note the asymmetry with the calculator above: it will tell you almost instantly that 999,999,999,989 is prime, and would need a fundamentally better algorithm to handle a number hundreds of digits long.

What a factorization is good for

Once a number is broken down, several other questions answer themselves.

Counting divisors. Add one to each exponent and multiply. 100 is 2² × 5², so it has (2 + 1)(2 + 1) = 9 divisors: 1, 2, 4, 5, 10, 20, 25, 50 and 100. 820 is 2² × 5 × 41, giving (2 + 1)(1 + 1)(1 + 1) = 12.

Greatest common divisor. Take each shared prime to the lower of its two exponents. For 100 = 2² × 5² and 820 = 2² × 5 × 41, the shared part is 2² × 5 = 20.

Lowest common multiple. Take every prime that appears in either number, to the higher exponent. Here that is 2² × 5² × 41 = 4,100.

Simplifying fractions. Factor the top and the bottom and cancel what they share, which is the same operation as dividing by the greatest common divisor.

Recognising perfect squares. A number is a perfect square exactly when every exponent in its factorization is even, which is why 100 = 2² × 5² is one and 820 is not.

How many primes are there?

Infinitely many, and Euclid proved it more than two thousand years ago with an argument that still fits in a paragraph. Suppose the primes were a finite list. Multiply them all together and add 1. The result leaves a remainder of 1 when divided by every prime on the list, so either it is itself prime or it has a prime factor nobody listed. Either way the list was incomplete.

They do thin out, though. There are 25 primes below 100 and 168 below 1,000, so the second stretch of 900 numbers yields fewer than six primes per hundred against the first hundred's 25. The prime number theorem puts a figure on the thinning: the count below x settles near x divided by the natural log of x, which predicts about 145 below 1,000 against the true 168.

The thinning is uneven rather than steady. Twin primes such as 11 and 13, or 17 and 19, sit two apart and keep appearing far out into the number line, while elsewhere long runs pass with none at all.

If you want every prime below some limit rather than the factors of one number, trial division is the wrong tool. The sieve of Eratosthenes is the right one: write out the numbers, cross off the multiples of 2, then of 3, then of each surviving number in turn, and whatever is left standing is prime.

Common mistakes

The first is stopping too early. 12 = 2 × 6 is a correct factorization but not a prime factorization, since 6 is composite. Keep going until nothing on the list can be broken down further.

The second is leaving 1 in the answer. Every number is divisible by 1, so including it adds nothing and can be repeated forever.

The third is forgetting repeats. 100 is 2 × 2 × 5 × 5, not 2 × 5. The distinct primes are 2 and 5, but the factorization needs each one as many times as it divides.

The fourth is testing every integer rather than every prime, and continuing past the square root. Both are wasted effort, and on a large number that waste is the whole problem.

Prime factorization of common numbers

The prime factorizations of the numbers from 2 to 150, and of the round hundreds up to 1,000.