Math
Prime factorisation calculator
Every whole number above one has exactly one prime factorisation. That uniqueness is the reason the primes are called the building blocks of arithmetic.
The fundamental theorem of arithmetic
Every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, ignoring order. So 360 = 23 × 32 × 5, and no other combination of primes multiplies to 360.
This uniqueness is why 1 is not counted as prime. If it were, 6 could be written as 2×3, or 1×2×3, or 1×1×2×3, and the theorem would collapse. Excluding 1 keeps factorisation unique.
Why trial division stops at the square root
If n has a factor larger than √n, the matching cofactor must be smaller than √n — and would already have been found. So checking divisors up to the square root is sufficient to determine primality, which cuts the work enormously. For a six-digit number, that is a thousand checks rather than a million.
Skipping even numbers after 2 halves it again. More refined sieves and probabilistic tests such as Miller-Rabin are used for genuinely large numbers, where trial division becomes hopeless.
Counting divisors without listing them
Each divisor is built by choosing an exponent for each prime, from zero up to its power in n. For 360 = 23 × 32 × 51, that is 4 × 3 × 2 = 24 divisors, without listing a single one.
A number is a perfect square exactly when every exponent is even, which is also exactly when the divisor count is odd — the only case where a divisor pairs with itself.
Why this underpins modern encryption
Multiplying two large primes is trivial; recovering them from the product is not. No known classical algorithm factors a general large semiprime in reasonable time, and RSA encryption rests entirely on that asymmetry.
Modern RSA keys use primes of 1,024 bits or more, giving products of well over 600 decimal digits. Trial division on such a number would take longer than the age of the universe. Shor's algorithm solves it efficiently on a quantum computer, which is why post-quantum cryptography is an active field — the security of RSA is a bet on factorisation staying hard.
Common questions
Is 1 a prime number?
No, by definition. A prime has exactly two distinct positive divisors, 1 and itself; the number 1 has only one. Excluding it is what makes prime factorisation unique.
What is the largest known prime?
The record is held by a Mersenne prime — a number of the form 2^p − 1 — found by the distributed GIMPS project. The records have run to tens of millions of digits and are broken every few years, so check a current source for the specific figure.
How do I draw a factor tree?
Split the number into any two factors, then keep splitting each composite branch until every leaf is prime. Different starting splits give different trees but always the same set of primes at the leaves — which is the fundamental theorem in visual form.
What is a perfect number?
One whose divisors, excluding itself, sum to the number: 6 = 1+2+3, and 28 = 1+2+4+7+14. They are rare, and it remains unknown whether any odd perfect number exists — an open problem more than two thousand years old.