Prime Factorization Calculator
Break any number into its prime factors (e.g. 360 = 2³ × 3² × 5) and check whether a number is prime.
1,162 views
How It Works
Prime factorization means writing a number as a product of its prime building blocks — for example 60 = 2² × 3 × 5. The fundamental theorem of arithmetic guarantees that every integer greater than 1 has exactly one such factorization (aside from reordering the factors): there is only one way to break 60 down into primes, no matter which order you try dividing it. This uniqueness is what makes prime factorization a meaningful, well-defined operation rather than a matter of choice.
The tool finds it by trial division: it first divides out every factor of 2 it can (counting how many times 2 goes in evenly), then moves to odd candidates — 3, 5, 7, 9, 11… — dividing out each as many times as it fits, up to the square root of whatever remains. Worked example for 360: divide by 2 three times (360→180→90→45, so 2³), then 45 is odd — divide by 3 twice (45→15→5, so 3²), then 5 remains and is itself prime (5¹). Result: 360 = 2³ × 3² × 5, and multiplying that back out — 8 × 9 × 5 — confirms 360. If no candidate up to √n divides the remaining number evenly, that remaining number is itself prime and closes out the factorization.
What to Know
Small and medium numbers factor almost instantly this way. But the same trial-division approach becomes computationally hard for very large numbers — hundreds of digits — because the number of candidates to check grows enormously, and no known efficient (polynomial-time) algorithm exists for general integers on classical computers. This asymmetry — multiplying two large primes together is fast, but factoring their product back apart is slow — is not just a curiosity, it is the exact security foundation of RSA public-key cryptography: a public key is built from the product of two huge secret primes, and breaking the encryption would require factoring that product, which is currently infeasible at the key sizes in use.
- 1 has no prime factorization at all — it is neither prime nor composite, and the "empty product" convention treats it as a special case.
- A number that survives trial division up to its own square root with nothing dividing it is, by definition, prime.
- Beyond cryptography, factorization underlies simplifying fractions, finding the greatest common divisor (GCD) and least common multiple (LCM), and determining how many divisors a number has.
Frequently Asked Questions
Is 1 a prime number?
No. Primes have exactly two distinct positive divisors; 1 has only one (itself). Excluding 1 keeps prime factorizations unique — the fundamental theorem of arithmetic would break down otherwise, since you could pad any factorization with extra factors of 1.
What is factorization used for?
Simplifying fractions, finding the GCD and LCM of two numbers, and — most famously — it underpins RSA cryptography, where the difficulty of factoring the product of two huge primes is what keeps encrypted internet traffic secure.
Why is factoring large numbers considered "hard"?
Trial division and its refinements need to check a number of candidates that grows very fast with the size of the input. No efficient classical algorithm is known to factor an arbitrary large number quickly, unlike multiplication, which is fast in both directions in principle — this gap is what cryptographers exploit.
How does factorization connect to RSA encryption?
An RSA public key is derived from multiplying two large randomly chosen primes together. Anyone can multiply them to get the public key, but reversing that step — factoring the product back into its two primes — is the computational wall that protects the private key.
What happens if I enter a prime number directly?
The tool finds no divisor up to its square root, so it reports the number itself as its only prime factor, raised to the first power — confirming it is prime rather than composite.
Similar Tools
Report a Problem
Prime Factorization Calculator
Comments
No comments yet — be the first to write one!