What is a prime number?

A prime number is a positive integer greater than 1 that has exactly two factors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... The number 2 is the only even prime — all other even numbers are divisible by 2. Primes become less frequent as numbers get larger, but there are infinitely many (proved by Euclid around 300 BCE).

Can prime factorization be used to find GCF and LCM?

Yes! For GCF, take the LOWEST exponent of each shared prime factor. For LCM, take the HIGHEST exponent of each prime factor across both numbers. For example, 72 = 2³ × 3² and 108 = 2² × 3³. GCF = 2² × 3² = 4 × 9 = 36. LCM = 2³ × 3³ = 8 × 27 = 216. This is more efficient than listing factors or multiples for large numbers.

What is a factor tree and how do I use it?

A factor tree is a visual diagram that breaks a number down into its prime factors step by step. Start with the number at the top. Draw two branches to a factor pair (any two numbers that multiply to the target). Continue branching each composite number until all branches end at prime numbers. The product of all leaf primes is the prime factorization.

Why is the prime factorization unique?

The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization (ignoring order). Euclid (around 300 BCE) proved the key lemma that a prime dividing a product divides one of the factors, and Gauss gave the first clear statement and proof of unique factorization in 1801. If factorizations were not unique, the entire edifice of number theory would collapse — divisibility, GCD, LCM, and much of modern mathematics depend on this uniqueness.

How do I know when to stop factoring?

You stop when every branch of the factor tree ends at a prime number. In the trial division method, you stop when the remaining number is less than the square of the next prime to test — at that point, what remains is prime. For example, after extracting all factors of 2 from 72, you get 9. Since 3² = 9 and 3 ≤ √9, you continue. After extracting 3s, you get 1, and you are done.

How is prime factorization used in cryptography?

RSA encryption, which secures most internet communication, relies on the fact that multiplying two large primes is easy, but factoring their product back into the two original primes is extremely difficult. A 2048-bit RSA key is the product of two ~300-digit primes. While this calculator factors any supported number (up to 9×10¹⁵) in milliseconds, no known classical algorithm can factor a properly chosen 600-digit number in practical time.

Prime Factors

Break any integer into its unique prime factors with an interactive factor tree. Detects perfect squares, cubes, and handles numbers up to one million.

✓ Tested formula & cited sources Checked against independent sources · Oct 14, 2026 Private: runs in your browser

Number

Enter a whole number from 2 up to 9,007,199,254,740,991 to find its prime factorization

Results

Prime Factorization

2^3 × 3^2

Prime Factors: 2, 3
Prime Factors (with multiplicity): 5

The formula

n = p₁ᵃ × p₂ᵇ × p₃ᶜ × ... (unique product of primes)

p₁, p₂, p₃...: Prime Factors
a, b, c...: Exponents

Worked example — Number 72

Prime Factorization = 2^3 × 3^2

Full explanation ↓

How Prime Factors Works

n = p₁ᵃ × p₂ᵇ × p₃ᶜ × ... (unique product of primes)

Every integer greater than 1 can be uniquely expressed as a product of prime numbers raised to exponents. This is the Fundamental Theorem of Arithmetic, which guarantees that every number has exactly one prime factorization (ignoring the order of factors). This uniqueness is what makes prime numbers the fundamental building blocks of all integers.

p₁, p₂, p₃...: Prime Factors — Prime numbers that divide n evenly. Primes are numbers greater than 1 with exactly two factors: 1 and themselves.
a, b, c...: Exponents — How many times each prime factor appears in the factorization. For example, in 72 = 2 × 2 × 2 × 3 × 3, the exponent of 2 is 3 and the exponent of 3 is 2.

A factor tree breaks a number down step by step until all branches end at prime numbers.

Worked Examples

Find the prime factorization of 72 using a factor tree.

number = 72

72 = 2³ × 3²

Starting with 72, split into 8 × 9. Then 8 = 2 × 4 = 2 × 2 × 2, and 9 = 3 × 3. Collecting primes: three 2s and two 3s, so 72 = 2³ × 3². The exponent 3 means 2 appears three times as a factor.

Check if 144 is a perfect square by examining its prime factorization.

number = 144

144 = 2⁴ × 3²

All exponents (4 and 2) are even numbers. This confirms 144 is a perfect square: √144 = 2² × 3¹ = 4 × 3 = 12. If any exponent were odd, 144 would not be a perfect square.

Use prime factorization to find the GCD and LCM of 84 and 90.

number = 84

84 = 2² × 3 × 7

84 = 2²×3×7 and 90 = 2×3²×5. For GCD: take lowest exponents of shared primes (2 and 3) → 2¹×3¹ = 6. For LCM: take highest exponents of all primes (2, 3, 5, 7) → 2²×3²×5×7 = 1260.

Understanding the Result

Prime factorization breaks a number into its fundamental prime building blocks. The Fundamental Theorem of Arithmetic states that every integer greater than 1 has a unique prime factorization — meaning there is only one way to write it as a product of primes (ignoring the order). This uniqueness is what makes prime numbers so important: they are the atoms of the number system. To find the prime factorization, divide the number by the smallest prime (2) as many times as possible, then move to the next prime (3), and continue until the result is 1.

For example, 72: divide by 2 three times to get 9, then divide by 3 twice to get 1, giving 72 = 2 × 2 × 2 × 3 × 3 = 2³ × 3². The factor tree visualization shows this process as a branching diagram. Prime factorization is essential for finding GCD and LCM (using shared and highest exponents), simplifying radicals, testing whether numbers are perfect squares or cubes, and understanding the structure of the number system.

Cryptography, particularly RSA encryption, relies on the fact that factoring large numbers into primes is computationally difficult.

How to Use

Enter any positive integer greater than 1 in the input field.
View the prime factorization as a multiplication expression of prime numbers with exponents.
See the interactive factor tree visualization that shows how the number breaks down step by step into its prime building blocks.
Check the total number of prime factors (with multiplicity) to understand the number's "factor depth."

Quick Reference

Smallest prime	2 (the only even prime)
First 10 primes	2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Perfect square	All exponents are even (e.g. 36 = 2²×3²)
Perfect cube	All exponents are multiples of 3
Divisibility by 2	Last digit is even
Divisibility by 3	Sum of digits divisible by 3
Divisibility by 5	Last digit is 0 or 5
Fundamental Theorem	Every integer > 1 has a unique prime factorization

Frequently Asked Questions

What is a prime number?: A prime number is a positive integer greater than 1 that has exactly two factors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... The number 2 is the only even prime — all other even numbers are divisible by 2. Primes become less frequent as numbers get larger, but there are infinitely many (proved by Euclid around 300 BCE).
Can prime factorization be used to find GCF and LCM?: Yes! For GCF, take the LOWEST exponent of each shared prime factor. For LCM, take the HIGHEST exponent of each prime factor across both numbers. For example, 72 = 2³ × 3² and 108 = 2² × 3³. GCF = 2² × 3² = 4 × 9 = 36. LCM = 2³ × 3³ = 8 × 27 = 216. This is more efficient than listing factors or multiples for large numbers.
What is a factor tree and how do I use it?: A factor tree is a visual diagram that breaks a number down into its prime factors step by step. Start with the number at the top. Draw two branches to a factor pair (any two numbers that multiply to the target). Continue branching each composite number until all branches end at prime numbers. The product of all leaf primes is the prime factorization.
Why is the prime factorization unique?: The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has exactly one prime factorization (ignoring order). Euclid (around 300 BCE) proved the key lemma that a prime dividing a product divides one of the factors, and Gauss gave the first clear statement and proof of unique factorization in 1801. If factorizations were not unique, the entire edifice of number theory would collapse — divisibility, GCD, LCM, and much of modern mathematics depend on this uniqueness.
How do I know when to stop factoring?: You stop when every branch of the factor tree ends at a prime number. In the trial division method, you stop when the remaining number is less than the square of the next prime to test — at that point, what remains is prime. For example, after extracting all factors of 2 from 72, you get 9. Since 3² = 9 and 3 ≤ √9, you continue. After extracting 3s, you get 1, and you are done.
How is prime factorization used in cryptography?: RSA encryption, which secures most internet communication, relies on the fact that multiplying two large primes is easy, but factoring their product back into the two original primes is extremely difficult. A 2048-bit RSA key is the product of two ~300-digit primes. While this calculator factors any supported number (up to 9×10¹⁵) in milliseconds, no known classical algorithm can factor a properly chosen 600-digit number in practical time.

Pro Tips

→To check if a number is a perfect square from its factorization: every exponent must be even. If 2 appears 4 times and 3 appears 2 times, the number is a perfect square. If any exponent is odd, it is not.
→Start dividing by 2 repeatedly until you get an odd number — this extracts all factors of 2 quickly. Then test odd numbers (3, 5, 7...) up to the square root. This is twice as fast as testing every integer.
→The number of trailing zeros in n! equals the exponent of 5 in its prime factorization (since there are always more 2s than 5s). For example, 100! ends in 24 zeros because floor(100/5) + floor(100/25) = 20 + 4 = 24.
→When building a factor tree by hand, start with the most obvious factor pair — even a bad split still converges to the same primes. There is no wrong path: 72 can split into 8×9 or 6×12 or 2×36, and all paths lead to 2³×3².

Limitations to Know

•This calculator accepts whole numbers up to 9,007,199,254,740,991 (2⁵³ − 1), the largest range in which a JavaScript number is exact. For numbers with hundreds of digits you need specialised software (quadratic sieve, general number field sieve) — the same difficulty that protects cryptography.
•The factor tree always splits the sorted list of prime factors in half, which keeps it shallow. Splitting differently (8 × 9 instead of 4 × 18, say) gives a different tree shape but the same prime leaves — the factorization is always identical.
•Factoring uses trial division by small primes, then deterministic Miller–Rabin primality tests (exact for every supported input) and Pollard rho, so even the product of two 8-digit primes factors instantly. It is not a general-purpose big-number factoring tool.

Sources

Was this calculator helpful?

Cite this calculator

TheCalcUniverse. "Prime Factorization Calculator — Factor Tree." TheCalcUniverse, 2026, https://thecalcuniverse.com/math/prime-factorization-calculator/. Accessed October 25, 2026.

Embed this calculator on your site

Free to embed. Paste this into any HTML page — it stays up to date automatically.

<iframe src="https://thecalcuniverse.com/embed/math/prime-factorization-calculator/"
  width="100%" height="620" frameborder="0" loading="lazy"
  title="Prime Factorization Calculator — Factor Tree"
  style="border:none;max-width:640px;margin:0 auto;display:block;">
</iframe>
<p style="text-align:center;font-size:12px;margin:4px auto;max-width:640px;">
  Calculator by <a href="https://thecalcuniverse.com/math/prime-factorization-calculator/">Prime Factorization Calculator — Factor Tree — TheCalcUniverse</a>
</p>

Open embed ↗