Prime Factorization Calculator

What prime factorization actually computes

Every integer greater than 1 can be written as a product of prime numbers in exactly one way, ignoring order. This is the Fundamental Theorem of Arithmetic, and it is the reason prime factorization is the bedrock of number theory. Factorizing a number means finding that unique set of prime building blocks together with how many times each appears. For example, 360 factors as 2³ × 3² × 5: three 2s, two 3s, and one 5, and no other combination of primes multiplies back to 360. This calculator accepts any integer up to 10¹⁵ and returns that factorization, the full list of divisors, an interactive factor tree, and a classification of the number — all computed in your browser with no data leaving your device.

How the algorithm finds the factors

The tool uses trial division: it tries dividing your number by 2, then 3, 4, 5, and so on, peeling off each prime completely before moving to the next candidate. The crucial optimisation is the stopping point. You only need to test divisors up to the square root of the number, because if n = a × b and both a and b exceeded √n, their product would exceed n. So once a candidate passes √n, whatever remains must itself be a single prime. To keep large inputs fast, the search is capped at the smaller of √n or one million, and the calculation runs on JavaScript's BigInt type so a 15-digit number never loses precision to floating-point rounding.

A worked example: factorizing 360

Type 360 and the engine proceeds step by step:

1. 360 is even, so divide by 2: 360 → 180 → 90 → 45. That is three 2s, giving 2³, and 45 remains.
2. 45 is no longer even. Try 3: 45 → 15 → 5. That is two 3s, giving 3², and 5 remains.
3. 5 is not divisible by 3, and 3 now exceeds √5, so 5 is itself prime. That is one 5.

The result is 2³ × 3² × 5. From those exponents the tool derives everything else: the number of divisors is (3+1)(2+1)(1+1) = 24, and it lists all 24 of them from 1 up to 360.

Reading the factor tree and divisor list

The SVG factor tree visualises the decomposition as branches, with prime leaves drawn as filled blue circles and composite intermediate values as grey circles. It is a teaching aid: it shows that no matter which factor you split off first, you arrive at the same prime leaves — a concrete demonstration of uniqueness. The divisor list below it is built by taking every combination of prime powers (each prime used 0 up to its exponent times), which is why a number with small primes and high exponents can have dozens of divisors while a large prime has only two.

GCD and LCM, and the identity that links them

The second section computes the greatest common divisor and least common multiple of two numbers. The GCD uses the Euclidean algorithm — repeatedly replace the larger number with its remainder against the smaller until one becomes zero, and the survivor is the GCD. The LCM is then found with the identity the tool relies on:

LCM(a, b) = a ÷ GCD(a, b) × b

This works because GCD(a, b) × LCM(a, b) = a × b for any two positive integers. For example, with 12 and 18: the GCD is 6, so the LCM is 12 ÷ 6 × 18 = 36. Dividing before multiplying also keeps the intermediate values small, which avoids overflow on large inputs.

What the classification badges mean

Each number is tagged using the sum of its proper divisors (all divisors except the number itself):

Perfect numbers are genuinely rare — only a handful exist below a billion (6, 28, 496, 8128, 33550336) — so most numbers you test will read as either abundant or deficient.

Common mistakes and edge cases

• Treating 1 as prime. The number 1 has only a single divisor, so it fails the "exactly two divisors" definition. The tool classifies it as a unit, neither prime nor composite. This is not pedantry — if 1 were prime, factorizations would no longer be unique.
• Confusing GCD with LCM. GCD is always ≤ the smaller input; LCM is always ≥ the larger input. If your result is the other way round, you have them swapped.
• Expecting instant results on huge semiprimes. A number that is the product of two large primes near 10¹⁵ is the hardest case for trial division, because no small factor exists to peel off. This is the same difficulty that makes large semiprimes useful in cryptography.
• Pasting decimals or negatives. The tool factorizes positive integers only; strip commas and spaces and it will parse the digits.