Prime Factorization by Trial Division

Breaks an integer into a product of primes by trial division, dividing by the smallest primes first. A number with a single prime factor is itself prime.

Explanation

Prime factorization rewrites an integer as a product of primes. Every integer of 2 or more has exactly one such factorization, up to the order of the factors. That uniqueness is the fundamental theorem of arithmetic.

This calculator uses trial division. Divide by 2 as many times as it goes, then by 3, and so on upward. Once the divisor squared exceeds whatever is left, the search stops; anything greater than 1 still remaining must itself be prime.

$n$ — the integer to factor, 2 or more
Prime factorization — the factors listed in increasing order
Number of prime factors — counted with repetition

Example

Factor $n = 360$ .

$360 \div 2 = 180$ , $180 \div 2 = 90$ , $90 \div 2 = 45$ , so 2 divides three times
$45 \div 3 = 15$ , $15 \div 3 = 5$ , so 3 divides twice
what remains, 5, is prime

So $360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5$ , or in exponent form

360 = 2^3 \times 3^2 \times 5

The number of prime factors, counting repeats, is 6.

Notes

1 is neither prime nor composite, so the input starts at 2.
A number whose factorization has a single factor is itself prime. 97 factors as just 97.
The count is of factors with multiplicity, not of distinct primes. For 360 that means three 2s, two 3s and one 5, giving 6 in total.
Trial division slows down badly on large inputs, so this calculator caps $n$ at $10^{12}$ .