What is prime factorization?
Prime factorization writes a whole number greater than 1 as a product of primes. The fundamental theorem of arithmetic says there’s only one way to do it, apart from the order you write the factors in. A prime is already its own factorization, while a composite number breaks into two or more primes.
How trial division and factor trees work
Trial division starts with 2, the smallest prime. Keep dividing while the answer is still a whole number, then move on to 3, 5, 7 and so on. When what’s left is 1, every prime factor has been found.
A factor tree shows the same process as a picture. Each branch splits into a prime and a smaller number. You can split a number in different ways and get trees that look different, but every finished tree ends with the same primes at the bottom.
For numbers whose factors are all large, trial division can take too long. After checking small primes up to 10,000, the calculator uses Pollard’s rho method to search for larger factors and Miller–Rabin testing to identify likely primes. For example, it can split 2^67 − 1 into 193,707,721 × 761,838,257,287 without exhaustive trial division. Frank Nelson Cole presented this factorization in 1903 after years of manual work.
Running time depends on the number’s structure and the visitor’s device. A product with a relatively small factor is usually easier to split than a 25- to 30-digit product of two similarly large primes. The calculator stops after a short browser-time budget, displays every factor it verified and labels any unsplit remainder as composite rather than presenting a guess.
Prime factorization example
For 360, repeated division produces 2, 2, 2, 3, 3 and 5, so 360 = 2³ × 3² × 5. The exponents also tell you how many factors 360 has: (3 + 1)(2 + 1)(1 + 1) = 24.
Where prime factorization is useful
Simplifying roots and powers
Factorization shows the repeated factors that can come out of a square root. Since 756 = 2² × 3³ × 7, the 2² and one pair of 3s come out, leaving √756 = 2 × 3 × √21 = 6√21. The calculator does this for you under “Simplified square root”.
Finding GCFs, LCMs and reducing fractions
Prime exponents make shared factors easy to spot. For 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7, taking the lower power of each shared prime gives the GCF, 2 × 3 × 7 = 42. Taking the higher power gives the LCM, 2² × 3² × 7 = 252.
Counting arrangements and divisors
If n = pᵃqᵇ, every factor of n uses between 0 and a copies of p and between 0 and b copies of q. That makes (a + 1)(b + 1) factors in all. It’s handy for factor-pair puzzles and for working out how many rectangles you can make from n squares.
Cryptography, at a very different scale
Some public-key systems, including RSA, rely on the difficulty of factoring products of very large primes. This calculator is an educational tool for inputs up to 30 digits and is not intended to analyse cryptographic keys.
Large-number prime-factorization puzzles
Why does 999,999 have so many small prime factors?
Its digits add up to 54, so it divides by 3 more than once. Finishing the job gives 999,999 = 3³ × 7 × 11 × 13 × 37, which has (3 + 1) × 2 × 2 × 2 × 2 = 64 factors.
What is the smallest number with exactly 18 factors?
The exponent pattern 2² × 3² × 5 gives (2 + 1)(2 + 1)(1 + 1) = 18 factors. Putting the biggest exponents on the smallest primes keeps the number as small as possible, so the answer is 180.
How can factorization prove that 176,400 is a square?
The calculator gives 176,400 = 2⁴ × 3² × 5² × 7². Every exponent is even, so halving them gives the square root: 2² × 3 × 5 × 7 = 420. So 176,400 = 420².