Prime Factor Finder

Every number factors exactly one way

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, ignoring order. 60 is 2 × 2 × 3 × 5 and there is no other combination of primes that multiplies to 60. This uniqueness is what makes prime factorisation useful rather than merely possible — it gives every number a canonical fingerprint.

How the factorisation is found

Trial division tests each prime in turn, dividing out every occurrence before moving on. You only need to test primes up to the square root of what remains: if no prime at or below the square root divides it, the remainder is itself prime. That is why checking whether 97 is prime requires testing only 2, 3, 5 and 7.

Why 1 is not prime

Not an arbitrary exclusion. If 1 counted as prime, factorisation would stop being unique — 6 would be 2 × 3, and also 1 × 2 × 3, and 1 × 1 × 2 × 3, endlessly. Excluding 1 is what preserves the theorem, and the same reasoning excludes it from being composite.

GCD and LCM fall straight out of it

With both numbers factorised, the greatest common divisor takes the lowest power of each shared prime and the least common multiple takes the highest power of every prime appearing in either. For 12 = 2²×3 and 18 = 2×3², the GCD is 2×3 = 6 and the LCM is 2²×3² = 36. This is why factorisation is taught before fraction arithmetic — reducing fractions and finding common denominators are the same operation underneath.

Difficulty at scale is what secures the internet

Multiplying two large primes is instant; recovering them from the product is not. RSA encryption rests entirely on that asymmetry. Numbers used in practice run to 2048 bits or more, and factoring one with known classical methods would take longer than the age of the universe. Shor's algorithm on a sufficiently large quantum computer would change this, which is what drives the current migration to post-quantum cryptography.

Reading the exponent form

360 = 2³ × 3² × 5 is more useful than the flat list, because the exponents make the structure visible. The number of divisors follows directly: add one to each exponent and multiply, so 360 has 4 × 3 × 2 = 24 divisors. A perfect square is exactly a number whose every exponent is even.