Prime Factorization Calculator

What is a prime number?

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. A whole number greater than 1 that is not prime is composite, because it can be built by multiplying smaller whole numbers; 12 = 3 × 4, for example. The number 1 is neither prime nor composite.

2 is the only even prime, since every other even number is divisible by 2. Euclid proved around 300 BC that there are infinitely many primes: multiply any finite list of primes together and add 1, and the result has a prime factor missing from the list. Primes thin out as numbers grow, but they never stop. The largest known primes have tens of millions of digits and are found by distributed computing projects.

What is prime factorization?

Prime factorization writes a composite number as a product of prime numbers. The fundamental theorem of arithmetic guarantees that every whole number greater than 1 has exactly one such factorization, apart from the order of the factors. So 100 = 2 × 2 × 5 × 5 = 2² × 5², and no other set of primes multiplies to 100. Primes are the building blocks of the whole numbers in the same way that atoms are the building blocks of molecules.

The simplest method is trial division. Divide the number by the smallest prime that goes into it evenly, write that prime down, and repeat with the quotient. Try 2 as long as the number is even, then 3, 5, 7 and so on. You only need to test primes up to the square root of what remains: if nothing up to that point divides it, what remains is itself prime. For 100, divide by 2 to get 50, by 2 again to get 25, then by 5 to get 5, which is prime.

A factor tree shows the same process as a diagram. Write the number at the top, split it into any two factors, and keep splitting each branch until every leaf is prime. 360 might split into 36 × 10, then 6 × 6 and 2 × 5, and finally 2 × 3 × 2 × 3 × 2 × 5. Different trees for the same number always end with the same leaves: 360 = 2³ × 3² × 5.

Factorizations make several other calculations easy. The greatest common factor of two numbers is the product of the primes they share, using the smaller exponent of each; the least common multiple uses every prime with the larger exponent. For 360 = 2³ × 3² × 5 and 84 = 2² × 3 × 7, the GCF is 2² × 3 = 12 and the LCM is 2³ × 3² × 5 × 7 = 2,520. The number of divisors is the product of each exponent plus one, so 360 has 4 × 3 × 2 = 24 divisors.

Factoring small numbers is easy, but no one knows a fast method for factoring very large numbers that are the product of two big primes. The RSA encryption that protects much internet traffic relies on that difficulty: multiplying two 300-digit primes is quick, while recovering them from the product would take ordinary computers an impractically long time.

Prime factorization of common numbers

The table lists the prime factorizations of the whole numbers from 2 to 101. Numbers whose factorization is the number itself are prime. Notice how the primes become less frequent as the numbers grow: there are 15 primes up to 50 but only 10 between 51 and 101.

Frequently asked questions