Prime Factorization Calculator

This prime factorization calculator (also called a prime factor calculator or prime decomposition calculator) breaks any whole number into the unique set of prime numbers that multiply to produce it. Enter a number, and the tool returns the factorization in exponential form, a flat list of prime factors, and a factor tree diagram. It also handles GCD and LCM using the prime factorization method, which is how most math textbooks teach it.

1. Enter any integer from 2 to 100,000 in the first input. The calculator finds the complete prime factorization instantly using trial division, which is the standard algorithm for numbers of this size.
2. Read the prime factorization in exponential form (for example 360 = 2³ × 3² × 5) and as a flat list of prime factors shown as individual chips. Both formats are useful: exponential form is compact, the flat list is easier to copy into homework.
3. View the factor tree for numbers up to 1,000 to see how the number is split step by step. Each branch divides by the smallest prime that works, which mirrors how to find prime factorization by hand.
4. Enter two numbers in the GCD and LCM section to find the greatest common divisor and least common multiple. The calculator shows each factorization so you can see where the shared primes come from, which is useful for simplifying fractions and finding common denominators.

Every result updates as you type, so you can test a range of numbers quickly. If you enter a prime (like 97 or 9973), the factorization is just the number itself, since a prime cannot be broken down further.

Prime factorization is built on one of the oldest results in number theory. This section walks through the definition, the standard algorithm, and how to use prime decomposition to compute the GCD and LCM of any pair of integers.

Definition: The Fundamental Theorem of Arithmetic

Every integer greater than 1 is either a prime number or can be written as a product of primes in exactly one way (up to the order of the factors). This is the Fundamental Theorem of Arithmetic, proved by Euclid around 300 BCE. Primes are the building blocks; composites are everything you can build by multiplying them. The number 1 is deliberately excluded, because including it would destroy the uniqueness: 12 = 2² × 3 = 1 × 2² × 3 = 1 × 1 × 2² × 3, and so on.

Trial Division Algorithm

Trial division is the standard way to find prime factorization by hand and is what the calculator above runs under the hood. Divide the number by 2 as many times as possible, then by 3, then 5, 7, 11, 13, and so on. You only need to test primes up to √n, because if a factor larger than √n existed, its partner factor would be smaller than √n and would have been found already.

Worked example: find the prime factorization of 84

  84 ÷ 2 = 42
  42 ÷ 2 = 21    (no more 2s, since 21 is odd)
  21 ÷ 3 = 7
   7 is prime, √84 ≈ 9.17, so stop.

  84 = 2 × 2 × 3 × 7
     = 2² × 3 × 7

Trial division is fast for numbers up to a few million. For numbers with hundreds of digits (used in cryptography), specialized algorithms like Pollard rho, the quadratic sieve, and the general number field sieve are needed, and even those take years of computer time for RSA-sized integers.

Sieve of Eratosthenes

If you need every prime up to some limit N (instead of factoring a single number), the Sieve of Eratosthenes is the classic tool. Write the integers 2, 3, 4, ... N in a list. Circle 2, then cross out every multiple of 2. Circle the next uncrossed number (3), cross out every multiple of 3. Repeat up to √N. Everything still circled or unmarked is prime. The sieve runs in roughly N log log N steps, which is fast enough to generate all primes below 10 million in under a second.

GCD from Prime Factorizations

Once you have the prime factorization of two numbers, the greatest common divisor is the product of each shared prime raised to the smaller of its two exponents. Primes that appear in only one of the factorizations do not contribute to the GCD.

Example: GCD(84, 30)

  84 = 2² × 3 × 7
  30 = 2  × 3 × 5

  Shared primes: 2 (min exponent 1), 3 (min exponent 1)
  GCD = 2¹ × 3¹ = 6

LCM from Prime Factorizations

The least common multiple takes every prime that appears in either factorization, raised to the larger of the two exponents. The LCM is the smallest positive integer that both numbers divide evenly.

Example: LCM(84, 30)

  84 = 2² × 3 × 7
  30 = 2  × 3 × 5

  All primes: 2 (max exp 2), 3 (max exp 1), 5 (max exp 1), 7 (max exp 1)
  LCM = 2² × 3 × 5 × 7 = 420

Check: GCD × LCM = 6 × 420 = 2520 = 84 × 30 ✓

That last line is a useful identity: for any two positive integers, GCD(a, b) × LCM(a, b) = a × b. Once you have one, you can get the other by dividing.

Quick Reference: Prime Factorizations of Common Numbers

The divisor count in the right column comes from the factorization directly: add 1 to each exponent and multiply. For 360 = 2³ × 3² × 5¹, that is (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24 divisors.

Prime factorization is not a classroom exercise for its own sake. It shows up any time you need to reduce fractions, compare ratios, align cycles, or secure data. This section covers the practical uses, why primes get called the atoms of integers, where the current frontier of known primes sits, and the handful of mistakes that cost students the most points on tests.

Real Uses: Fractions, LCM, and RSA Cryptography

The most common day-to-day application is simplifying fractions. Divide the numerator and denominator by their GCD, and the fraction is in lowest terms. For 84/30, the GCD is 6, so 84/30 reduces to 14/5. Adding fractions needs the LCM of the denominators as the common denominator: 1/6 + 1/4 uses LCM(6, 4) = 12, giving 2/12 + 3/12 = 5/12.

RSA encryption, which still secures a large share of internet traffic, relies on the fact that multiplying two large primes is fast but factoring their product is very slow. A 2048-bit RSA public key is the product of two primes each around 1024 bits long. Recovering those primes would break the key, but no known algorithm can do so in a reasonable time on classical hardware. The entire system rests on prime factorization being hard at scale.

Other applications: gear ratio design (LCM tells you after how many revolutions two gears realign), music theory (cycle lengths in rhythmic patterns), and hash table sizing (prime-number bucket counts reduce collisions for certain hash functions).

Why Primes Are the Atoms of Integers

Chemists call atoms the building blocks of matter because every molecule is a unique combination of them. Primes play the same role in arithmetic. Every integer above 1 has exactly one prime factorization, and there is no way to break a prime further. This uniqueness is what makes primes useful: you can compare two numbers, simplify a fraction, or check divisibility just by looking at their prime factor sets.

A number is divisible by another if and only if the smaller number's prime factorization is contained in the larger one's. 360 is divisible by 60 because 60 = 2² × 3 × 5 and 360 = 2³ × 3² × 5, and every prime power in 60 is present in 360 at an equal or larger exponent.

Largest Known Primes and Mersenne Records

Mathematicians have been chasing ever-larger primes for centuries. The current record-holders are almost all Mersenne primes, which have the form 2ᵖ − 1 where p is itself prime. As of 2024, the largest known prime is 2⁸²⁵⁸⁹⁹³³ − 1, which has more than 24 million digits. It was discovered by the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project that has found the majority of the largest known primes. Writing the number out in full would fill roughly 10,000 printed pages.

Euclid proved around 300 BCE that there are infinitely many primes, so the record will keep rising. What makes each new one interesting is not that it exists, but that someone verified it.

Common Mistakes When Finding Prime Factorizations

Three mistakes show up over and over in homework. First, stopping too early. Writing 24 = 2 × 12 is not a prime factorization, because 12 is not prime. You have to keep going: 12 = 2 × 6, and 6 = 2 × 3, so 24 = 2 × 2 × 2 × 3 = 2³ × 3. A factorization is only complete when every factor on the right side is prime.

Second, including 1 as a factor. By convention, 1 is not prime. A factorization like 18 = 1 × 2 × 3² is incorrect; the answer is just 2 × 3². If 1 were a factor, there would be infinitely many ways to factor any number, and the uniqueness that makes the theorem useful would vanish.

Third, missing repeated primes. For 72, it is easy to write 72 = 8 × 9 and think you are done, but 8 = 2³ and 9 = 3², so 72 = 2³ × 3². The exponents matter. A factorization of 72 that just says "2 and 3" loses all the information about how many copies of each prime you need. Always write the exponent or list each prime the right number of times.

If the calculator above disagrees with your hand-written answer, one of these three mistakes is almost always the cause.