Prime Factorization Calculator
Enter a number and the prime factorization calculator returns its prime factors, the division steps that found them, and the divisor count that falls out of the exponents.
Prime factorization
- Expanded
- 2 x 2 x 2 x 3 x 3 x 5
- Distinct primes 3 distinct primes, 6 factors in total.
- 2, 3, 5
- Dividing out each prime in turn Divide by the smallest prime that goes in, repeat on the quotient, stop at 1. The divisors used are the factorization.
- 360 / 2 = 180 180 / 2 = 90 90 / 2 = 45 45 / 3 = 15 15 / 3 = 5 5 / 5 = 1
- Number of divisors Multiply one more than each exponent: (3 + 1) x (2 + 1) x (1 + 1) = 24. A divisor picks each prime to a power from 0 up to its exponent, so there are that many combinations.
- 24
- Sum of divisors
- 1,170
- All divisors
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
- Perfect square or cube? A number is a perfect square exactly when every exponent is even, and a perfect cube exactly when every exponent is a multiple of three. The factorization answers this with no square roots taken.
- neither
- The factorization is unique. Every integer above 1 has exactly one multiset of primes multiplying to it, which is the fundamental theorem of arithmetic. It is also the reason 1 is not counted as prime.
- Found by trial division to the square root, which is fast up to about a trillion. Beyond that, factorization becomes genuinely hard, and that difficulty is what RSA encryption rests on.
How the Prime Factorization Calculator works
Every whole number above 1 is either prime or a product of primes, and that product is unique up to the order of the factors. This is the fundamental theorem of arithmetic, and it is the reason prime factorization is worth computing at all: the factorization is a complete description of the number's multiplicative structure, from which a surprising amount follows immediately.
Finding it by hand is a ladder. Divide by the smallest prime that goes in, then repeat on the quotient:
360 / 2 = 180 180 / 2 = 90 90 / 2 = 45 45 / 3 = 15 15 / 3 = 5 5 / 5 = 1
So 360 = 2 x 2 x 2 x 3 x 3 x 5, which in exponent form is 2^3 x 3^2 x 5. The two forms are used for different things: the expanded one for showing work, the exponent one for everything else.
The uniqueness is what makes 1 excluded from the primes. If 1 were prime, 6 could be 2 x 3 or 1 x 2 x 3 or 1 x 1 x 2 x 3, and the theorem would be false. Excluding it is a definitional choice made to keep the theorem clean, not an observation about 1.
Several things fall straight out of the exponents, with no further computation.
The divisor count is the product of one more than each exponent. For 2^3 x 3^2 x 5 that is (3+1)(2+1)(1+1) = 24, so 360 has exactly 24 divisors. The reason is combinatorial: a divisor is built by choosing each prime to a power from 0 up to its exponent, so there are 4 choices for the 2, 3 for the 3 and 2 for the 5.
Perfect squares are exactly the numbers whose every exponent is even, because a square's factorization is its root's doubled. 360 is not a square (the 3 and 1 exponents are odd); 900 = 2^2 x 3^2 x 5^2 is, and its root is 2 x 3 x 5 = 30. Perfect cubes are the ones whose exponents are all multiples of three. No square roots need to be taken to decide either.
GCF and LCM come from comparing two factorizations prime by prime: lowest power of each shared prime for the GCF, highest power of every prime for the LCM. And simplifying a square root is the same operation: pull out one copy of every squared pair, which is why sqrt(360) = 6sqrt(10).
The method here is trial division up to the square root, which is enough for anything a form can reasonably accept. Only checking to the square root is sound because if n = a x b then one of a and b is at most sqrt(n); and the loop steps by 6k plus or minus 1 because every prime above 3 has that form, which skips two thirds of the candidates.
Past about 20 digits, this stops working, and the fact that nothing much better exists is economically significant. Multiplying two 300-digit primes is instant; recovering them from the product is beyond any existing computer. RSA encryption is built on exactly that asymmetry, which is why a mundane school exercise and modern cryptography are the same problem at different scales.
Prime Factorization Calculator FAQ
What is the prime factorization of 360?
2^3 x 3^2 x 5, or expanded, 2 x 2 x 2 x 3 x 3 x 5. Divide by 2 three times to reach 45, by 3 twice to reach 5, and by 5 once to reach 1. The divisors you used are the factorization.
Why isn't 1 a prime number?
Because including it would break the uniqueness of factorization. If 1 were prime then 6 could be written as 2 x 3, 1 x 2 x 3, or 1 x 1 x 2 x 3, and the fundamental theorem of arithmetic would be false. Excluding 1 is a definitional choice made to keep that theorem true.
How do I find how many divisors a number has?
Add one to each exponent in the prime factorization and multiply. 360 = 2^3 x 3^2 x 5 gives (3+1)(2+1)(1+1) = 24 divisors. The logic is that a divisor chooses each prime to a power between 0 and its exponent, so the count is the product of the number of choices.
How can I tell if a number is a perfect square from its factors?
Every exponent in its prime factorization is even. 900 = 2^2 x 3^2 x 5^2 is a perfect square and its root is 2 x 3 x 5 = 30. 360 = 2^3 x 3^2 x 5 is not, because the 2 and the 5 have odd exponents. The same test with multiples of three identifies perfect cubes.