Prime Factorization Calculator
Find the prime factors of any positive integer and check if a number is prime.
What Is Prime Factorization?
Prime factorization expresses any whole number greater than 1 as a unique product of prime numbers. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization (ignoring the order of factors). For example: 360 = 2³ × 3² × 5, and no other combination of primes multiplies to give 360. This uniqueness makes prime factorization a foundational tool across number theory, cryptography, and everyday math like simplifying fractions.
How Prime Factorization Works
The simplest method is trial division: repeatedly divide the number by the smallest prime that divides it evenly, and continue with the quotient until you reach 1. Starting with 360: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. Reading the divisors: 2, 2, 2, 3, 3, 5 — which is written as 2³ × 3² × 5. You only need to test primes up to the square root of the number — any factor above the square root must pair with a factor below it.
Why Prime Factorization Matters
Prime factorization underlies several practical calculations. Finding the GCF (Greatest Common Factor) and LCM (Least Common Multiple) of numbers — essential for fraction arithmetic — is easiest when you have the prime factorizations of both numbers. In cryptography, the difficulty of factoring very large numbers into primes is the security foundation of RSA encryption, the most widely used public-key cryptographic system. If you have a 2048-bit RSA key, its security rests on the computational difficulty of factoring a 617-digit number.
Frequently Asked Questions
What is a prime number?
A prime number is a natural number greater than 1 with exactly two divisors: 1 and itself. The first several primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... 2 is the only even prime. 1 is not prime (it has only one divisor). There are infinitely many primes — Euclid proved this around 300 BC.
How do I check if a number is prime?
Divide it by every prime up to its square root. If none divide evenly, it is prime. For a number n, you only need to test primes up to √n because if n has a factor larger than √n, the corresponding paired factor must be smaller than √n — and you would have found that one already. For n = 97: √97 ≈ 9.85, so test 2, 3, 5, 7. None divide 97 evenly, so 97 is prime.
What is the largest known prime number?
As of recent records, the largest known prime has tens of millions of digits and is a Mersenne prime — a prime of the form 2^n - 1. The Great Internet Mersenne Prime Search (GIMPS) distributed computing project discovers new record primes periodically using volunteer computers. Finding large primes is computationally intensive but has practical value for cryptography research.
How is prime factorization used to find GCF and LCM?
To find GCF: write the prime factorizations of both numbers and take the lowest power of each shared prime factor. GCF(12, 18): 12 = 2² x 3, 18 = 2 x 3². Shared primes: 2 (min power: 1) and 3 (min power: 1). GCF = 2 x 3 = 6. To find LCM: take the highest power of each prime that appears in either number. LCM(12, 18): 2² x 3² = 36.
What are composite numbers?
A composite number is any positive integer greater than 1 that is not prime — it has at least one factor other than 1 and itself. Every composite number can be broken down into prime factors. Examples: 4, 6, 8, 9, 10, 12, 14, 15, 16... The number 1 is neither prime nor composite by mathematical convention.