About the Prime Factorization

The prime factorization calculator decomposes any positive integer into its prime factors — the prime numbers that multiply together to give the original number. By the fundamental theorem of arithmetic, this decomposition is unique up to the order of the factors, so every integer greater than 1 has exactly one prime factorization. This makes prime factorization a cornerstone of number theory.

Prime factorization is the key to many other number-theoretic operations. The greatest common divisor of two numbers can be found by taking the minimum power of each shared prime factor, and the least common multiple by taking the maximum power of each prime factor that appears. Simplifying fractions, finding square roots that reduce to rational numbers, and testing whether a number is a perfect power all rely on knowing the prime factorization.

The calculator uses trial division, the simplest factorization method, which is exact for any input up to about 10^15 and runs quickly for most practical inputs. It returns the factorization in both expanded form (a sequence of primes multiplied together) and exponential form (each prime raised to its power), and it tells you whether the input itself is prime.

How It Works

The algorithm divides out prime factors in increasing order. Starting with the smallest prime, 2, it repeatedly divides the input by that prime as long as the remainder is zero, recording each successful division as a factor. When the input is no longer divisible by the current candidate, the candidate is incremented and the process repeats:

n = input
d = 2
while d * d <= n:
  while n mod d == 0:
    record d as a factor
    n = n / d
  d = d + 1
if n > 1:
  record n as a factor (it is prime)

The loop condition d * d <= n is the key optimisation: once the candidate exceeds the square root of the remaining value, that remaining value must itself be prime, so it is recorded directly. This reduces the number of divisions from O(n) to O(sqrt(n)), making the algorithm practical for large inputs.

The factorization is unique by the fundamental theorem of arithmetic. Two different lists of prime factors cannot multiply to the same integer, which is why prime factorization is sometimes called the "DNA" of an integer. The exponential form groups repeated factors: 360 = 2^3 x 3^2 x 5 is more compact than 2 x 2 x 2 x 3 x 3 x 5 and makes the structure of the number clearer.

Worked Examples

Using the default input 360, the calculator finds that 360 is divisible by 2 three times (360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45), leaving 45. Then 45 is divisible by 3 twice (45 / 3 = 15, 15 / 3 = 5), leaving 5. Since 5 is prime, it is recorded directly. The expanded factorization is 2 x 2 x 2 x 3 x 3 x 5, and the exponential form is 2^3 x 3^2 x 5.

For a prime input like 97, the loop runs through candidates 2, 3, 4, ..., 9 without finding any factor (since 9 squared is 81, which is less than 97, but 10 squared is 100, which exceeds 97). At that point the remaining value 97 is larger than 1, so it is recorded as a prime factor. The calculator correctly identifies 97 as prime.

For a perfect power like 1024, the calculator divides by 2 ten times in succession, giving the factorization 2^10. This makes it immediately obvious that 1024 is a power of 2 and that its square root is 2^5 = 32, a clean integer.

When to Use This Tool

Use the prime factorization calculator when you need to:

Simplify square roots by extracting square factors (for example, sqrt(72) = 6 * sqrt(2)).
Find the GCD or LCM of two numbers by comparing their prime factorizations.
Test whether a number is a perfect square, cube, or higher power.
Reduce fractions to lowest terms by cancelling shared prime factors.
Work through number theory or cryptography exercises.
Understand the structure of a number for teaching or self-study.
Verify hand calculations in a discrete mathematics course.

Limitations & Disclaimer

This calculator uses trial division, which is exact but becomes slow for inputs larger than approximately 10^15. It does not implement advanced factorisation algorithms such as Pollard's rho or the quadratic sieve, and it cannot factor numbers larger than JavaScript's safe integer range (about 9 * 10^15) without losing precision. For cryptographic factorisation tasks, use a dedicated big-integer library. See our disclaimer for full details.

Frequently Asked Questions

What is the fundamental theorem of arithmetic?

It states that every integer greater than 1 can be written as a unique product of prime numbers, up to the order of the factors. This is why prime factorization is sometimes called the DNA of an integer: it is a complete and unambiguous description of the number's multiplicative structure.

Why does the loop stop at the square root?

If a number n has a factor larger than its square root, the corresponding co-factor must be smaller than the square root. So once the trial divisor exceeds the square root of the remaining value, any remaining factor must be prime, and it can be recorded directly without further division.

What is the difference between expanded and exponential form?

Expanded form lists each prime factor separately, such as 2 x 2 x 2 x 3 x 3 x 5. Exponential form groups repeated factors, such as 2^3 x 3^2 x 5. Both represent the same number, but exponential form is more compact and makes the structure clearer.

How large a number can this calculator handle?

Trial division works exactly for any integer up to about 10^15 in a browser. Beyond that, the loop count grows and the calculation slows. For very large inputs, specialised algorithms such as Pollard's rho or the general number field sieve are used, but those are beyond the scope of this tool.

What makes a number prime?

A prime number has exactly two positive divisors: 1 and itself. The calculator detects primes because the loop completes without finding any factor, and the remaining value equals the original input, so the factorization consists of the single number itself.

Can prime factorization help with fractions?

Yes. To simplify a fraction, find the prime factorizations of the numerator and denominator, cancel any common prime factors, and multiply the remaining factors. This is the systematic version of dividing by the GCD.

Last updated: July 21, 2026 · Author: HT99 Tools Editorial Team · Reviewed by: HT99 Tools Editorial Team