Break Any Number Into Prime Factors
Last reviewed: April 2026
Prime factorization breaks any composite number into the product of its prime factors — the fundamental building blocks of all integers. Every integer greater than 1 is either prime (divisible only by 1 and itself) or can be expressed as a unique product of primes (the Fundamental Theorem of Arithmetic). For example, 84 = 2² × 3 × 7. This decomposition is unique for every number and has profound applications in cryptography, number theory, and computer science. For related tools, see our Combination Calculator and Statistics Calculator.
Trial division is the simplest method: divide by 2, then 3, then 5, and continue through successive primes up to the square root of the number. Each time a prime divides evenly, record it and continue dividing. If a remainder greater than 1 exists after reaching the square root, it's itself a prime factor. This calculator handles numbers up to 1 billion efficiently. For much larger numbers, more advanced algorithms like Pollard's rho or the quadratic sieve are needed.
RSA encryption — the foundation of internet security — relies on the difficulty of factoring very large numbers (hundreds of digits). Finding GCD and LCM uses prime factorizations. Simplifying fractions requires finding common factors. In music theory, frequency ratios of harmonious intervals are small prime ratios. Understanding prime factorization builds mathematical intuition that applies across disciplines.
| Number | Prime Factors | Exponent Form |
|---|---|---|
| 12 | 2 × 2 × 3 | 2² × 3 |
| 60 | 2 × 2 × 3 × 5 | 2² × 3 × 5 |
| 100 | 2 × 2 × 5 × 5 | 2² × 5² |
| 360 | 2 × 2 × 2 × 3 × 3 × 5 | 2³ × 3² × 5 |
| 1,000 | 2 × 2 × 2 × 5 × 5 × 5 | 2³ × 5³ |
Every integer greater than 1 is either a prime number or can be represented as a unique product of prime factors, regardless of the order. This statement — the Fundamental Theorem of Arithmetic — is one of the most important results in all of mathematics. "Unique" means there is exactly one way to factor any number into primes (ignoring order): 360 is always 2³ × 3² × 5, never something else. This uniqueness is what makes prime factorization so powerful as a mathematical tool. It underlies the structure of divisibility, the computation of greatest common divisors and least common multiples, and the security of modern encryption systems.
The trial division method works by systematically dividing the number by the smallest available prime. Start with 2 and keep dividing as long as it divides evenly. Then move to 3, then 5, then 7, and continue through successive primes. You only need to test primes up to the square root of the remaining number — if no prime up to that point divides it, the remaining number is itself prime. For example, factoring 360: divide by 2 → 180, by 2 → 90, by 2 → 45 (no more 2s), by 3 → 15, by 3 → 5, and 5 is prime. Result: 2³ × 3² × 5. The square root optimization is critical for efficiency — to factor a number up to 1 billion, you only need to test primes up to 31,623.
| Range | Count of Primes | Notable Primes |
|---|---|---|
| 1–100 | 25 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 |
| 100–200 | 21 | 101, 103, 107, 109, 113, 127, 131, ... |
| 200–500 | 42 | 211, 223, 227, 229, 233, ... |
| 500–1,000 | 73 | 503, 509, 521, 523, ... |
Prime factorization provides the most intuitive method for computing the greatest common divisor (GCD) and least common multiple (LCM) of two or more numbers. The GCD takes the minimum exponent of each shared prime factor, while the LCM takes the maximum exponent of every prime factor present in any of the numbers. For 360 (2³ × 3² × 5) and 504 (2³ × 3² × 7): GCD = 2³ × 3² = 72 (shared factors at minimum powers), LCM = 2³ × 3² × 5 × 7 = 2,520 (all factors at maximum powers). This method scales to any number of integers and provides clear insight into why the GCD and LCM have the values they do.
RSA encryption — the algorithm securing most internet transactions, email encryption, and digital signatures — depends entirely on the difficulty of factoring large numbers. RSA works by multiplying two very large prime numbers (each 150+ digits) to produce a public key. Encrypting a message using this public key is easy (multiplication), but decrypting it requires knowing the original prime factors — and no known algorithm can factor a 300-digit number in a reasonable time using current computers. The largest RSA number ever factored (RSA-250, 250 digits) required approximately 2,700 CPU-core-years of computation in 2020. Current RSA keys use 2,048-bit or 4,096-bit keys (617 or 1,234 digits), which are far beyond the reach of classical factoring algorithms. Quantum computers running Shor's algorithm could theoretically factor these numbers efficiently, which is why the cryptography community is actively developing post-quantum encryption standards.
Understanding prime factors illuminates common divisibility rules. A number is divisible by 6 if and only if it is divisible by both 2 and 3 (the prime factors of 6). Divisibility by 12 requires factors of 2² and 3. Divisibility by 15 requires factors of 3 and 5. These rules extend to any composite number: to check if N is divisible by some composite C, verify that N's prime factorization includes all of C's prime factors at equal or greater exponents. For quick divisibility checks: divisible by 2 if the last digit is even; by 3 if digit sum is divisible by 3; by 5 if the last digit is 0 or 5; by 7 requires actual division or the doubling-subtraction trick; by 11 if the alternating digit sum is divisible by 11.
To simplify any fraction to its lowest terms, find the prime factorization of both the numerator and denominator, then cancel all shared factors. For 84/120: 84 = 2² × 3 × 7, and 120 = 2³ × 3 × 5. Cancel the shared 2² and 3 to get 7/10. This method always produces the correct simplified fraction in one step, unlike the repeated division approach where you might simplify 84/120 → 42/60 → 21/30 → 7/10 in three steps. For fractions with large numbers, prime factorization is the most reliable simplification method because it identifies the complete GCD immediately.
→ Start with small primes. Always begin trial division with 2, then 3, then 5. These three primes alone factor out the majority of composite numbers you will encounter in everyday math.
→ Stop at the square root. You never need to test primes larger than √n. If no prime up to that point divides n, then n itself is prime.
→ Use factorization for LCM shortcut. Finding the LCM of multiple numbers by listing multiples is tedious. Prime factorization gives the answer directly by taking the highest power of each prime across all numbers.
See also: Combination Calculator · Binomial Probability · Binary Calculator · Equation Solver
Twin primes are pairs of primes separated by exactly 2 — such as (3,5), (11,13), (17,19), (29,31), and (41,43). Whether infinitely many twin primes exist remains one of the great unsolved problems in mathematics (the twin prime conjecture). As numbers grow larger, primes become less frequent — the prime counting function π(n) approximates n/ln(n), meaning roughly 1 in every 23 numbers near 10 billion is prime. The gaps between consecutive primes grow on average but remain unpredictable in detail. The largest known prime, discovered in 2024, has over 41 million digits and was found using the Great Internet Mersenne Prime Search (GIMPS). These massive primes are Mersenne primes of the form 2^p − 1, where p is itself prime.
→ Run multiple scenarios. Try different inputs to understand how each variable affects the result. This builds practical intuition beyond just getting a single answer.
→ Use accurate inputs for reliable results. The output is only as good as the input. Use measured values rather than rough estimates whenever possible.
→ Bookmark for quick access. Save this page for instant reference — no need to search for it again the next time you need this calculation.
→ Explore related tools. Check the related calculators section below for tools that complement this one — many calculations work best in combination.
See also: Permutation Calculator · GCD & LCM Calculator · Factorial & Combinations Calculator · Matrix Determinant Calculator · Binomial Probability Calculator