How trial division works
Trial division is the most direct way to factor a number by hand or in code. You start with the smallest prime, 2, and divide as many times as it goes in evenly. Each successful division peels off one prime factor and shrinks the number you still have to factor.
Once 2 no longer divides cleanly, you move up to the next candidate and repeat. A useful shortcut is that you only need to test divisors up to the square root of the remaining value: if nothing in that range divides it, whatever is left must itself be prime.
- Divide out every factor of 2 first
- Continue with 3, 5, 7 and onward, skipping even numbers
- Stop testing once a divisor squared exceeds the remainder
- Any leftover value greater than 1 is the final prime factor
Reading the factorization
The result is written as a product of primes, with exponents recording repeated factors. For example, 360 = 2³ × 3² × 5 means three 2s, two 3s, and one 5 multiplied together. Multiplying those out always returns the original number exactly.
The plain list of prime factors is handy when you need each factor separately rather than the grouped form, for instance when comparing two numbers to find shared factors.
Where prime factorization is useful
Breaking numbers into primes is the foundation for several other arithmetic tasks. It lets you compute the greatest common factor and least common multiple cleanly, and it underpins simplifying fractions and reducing radicals.
- Find the GCF by multiplying the primes two numbers share
- Find the LCM by taking the highest power of every prime that appears
- Simplify fractions by cancelling common prime factors
- Check whether a number is a perfect square by looking for all-even exponents
Common mistakes and limits
Prime factorization is only defined for whole numbers of 2 or greater. The numbers 0 and 1 have no prime factorization, and negative numbers are handled by factoring their absolute value separately from the sign.
Trial division is fast for everyday numbers but slows down dramatically for very large values with big prime factors, which is exactly why factoring is used as the basis for some encryption. For ordinary use the time is negligible.
Formula
n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖFrequently asked questions
- What does the small raised number mean?
- It is an exponent: 2³ means 2 × 2 × 2. It records how many times that prime divides the number.