๐ข Factor Tree ยท Division Ladder ยท GCF & LCM ยท All Factors
Prime Factorization Calculator
Break any number into its prime factors instantly. See the factor tree, division ladder, all factors, divisibility checks, and GCF/LCM for multiple numbers.
Enter a Number
+ Find GCF & LCM for multiple numbers
2
3
4
Try:
Enter a number above
Prime factorization, factor tree, and divisibility will appear here
Prime Factors
Unique Primes
โ
Total Factors
โ
Is Prime?
โ
Perfect Square?
โ
Division Ladder (Step-by-Step)
Factor Tree
All Factors
Divisibility Check
What Is Prime Factorization?
Prime factorization is the process of expressing a composite number as a product of its prime factors โ prime numbers that multiply together to produce the original number. Every integer greater than 1 is either prime (divisible only by 1 and itself) or can be uniquely expressed as a product of primes. This is the Fundamental Theorem of Arithmetic โ one of the most important results in all of mathematics. For example: 360 = 2ยณ ร 3ยฒ ร 5. No matter how you factor 360, you'll always arrive at this same set of prime factors. For related operations, see our Common Factor Calculator.
The Division Ladder Method
Trial Division Algorithm
1. Start with the smallest prime (2)
2. Divide n by the prime โ if divisible, record it and continue with the quotient
3. If not divisible, try the next prime (3, 5, 7, 11, 13...)
4. Stop when the quotient is 1 (or a prime itself)
Example: 360 โ 360รท2=180 โ 180รท2=90 โ 90รท2=45 โ 45รท3=15 โ 15รท3=5 โ 5 is prime โ 2ยณร3ยฒร5
Divisibility Rules โ Quick Reference
| รท | Divisibility Rule | Example |
|---|---|---|
| 2 | Last digit is even (0, 2, 4, 6, 8) | 360 โ ends in 0 โ |
| 3 | Sum of digits is divisible by 3 | 360 โ 3+6+0=9 รท 3 โ |
| 4 | Last two digits form a number divisible by 4 | 360 โ 60 รท 4 = 15 โ |
| 5 | Last digit is 0 or 5 | 360 โ ends in 0 โ |
| 6 | Divisible by both 2 and 3 | 360 โ even AND digit sum=9 โ |
| 7 | Double last digit, subtract from rest; result divisible by 7 | No simple shortcut โ just divide |
| 8 | Last three digits divisible by 8 | 360 โ 360 รท 8 = 45 โ |
| 9 | Sum of digits divisible by 9 | 360 โ 3+6+0=9 รท 9 โ |
| 10 | Last digit is 0 | 360 โ ends in 0 โ |
| 11 | Alternating digit sum divisible by 11 | 360 โ 3โ6+0=โ3, not divisible by 11 |
| 12 | Divisible by both 3 and 4 | 360 โ digit sum=9 AND 60รท4=15 โ |
Uses of Prime Factorization
GCF & LCM
GCF uses the minimum power of shared primes. LCM uses the maximum power of all primes. See our Common Factor Calculator.
Simplifying Fractions
Divide numerator and denominator by their GCF to reduce. Use our Fraction Calculator for step-by-step simplification.
Cryptography
RSA encryption relies on the difficulty of factoring large numbers (hundreds of digits) into primes. The security of the internet depends on this mathematical hardness.
Perfect Squares & Roots
A number is a perfect square if all prime factors appear in even exponents. For example, 36 = 2ยฒ ร 3ยฒ โ both exponents even โ โ36 = 6.
Frequently Asked Questions
Common questions about prime factorization, prime numbers, and factor trees
A prime number is any integer greater than 1 that has exactly two factors: 1 and itself. The first prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37โฆ Key facts: 2 is the only even prime number (all other even numbers are divisible by 2). 1 is not prime โ it has only one factor. There are infinitely many prime numbers (proved by Euclid around 300 BC). A number is prime if it has no divisors between 2 and its square root. When this calculator shows "Is Prime? โ", the number itself is one of these special numbers โ it cannot be factorized into smaller factors. Use our Common Factor Calculator to explore relationships between primes.
A factor tree is a visual diagram that shows how a number is broken down into its prime factors through successive factorizations. Starting with the original number at the top, you branch it into any two factors, then continue branching each composite factor until all branches end in primes. For example, 36 can branch as: 36 โ 4 ร 9 โ (2 ร 2) ร (3 ร 3) = 2ยฒ ร 3ยฒ. Alternatively: 36 โ 6 ร 6 โ (2 ร 3) ร (2 ร 3) = 2ยฒ ร 3ยฒ. Both paths reach the same result โ this is guaranteed by the Fundamental Theorem of Arithmetic. The factor tree displayed by this calculator shows one canonical path using the smallest prime divisor at each step. See our Long Division Calculator for the underlying division operations.
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number or can be represented as a unique product of prime numbers (up to ordering). This uniqueness is crucial โ it means there is exactly one prime factorization for any number. For example, 360 = 2ยณ ร 3ยฒ ร 5. No matter how you factor 360 โ whether you start with 2 ร 180, or 4 ร 90, or 6 ร 60 โ you'll always arrive at 2ยณ ร 3ยฒ ร 5 when fully simplified. This uniqueness property underpins almost all of number theory and has direct applications in cryptography, computer science, and algebra. It was first proved rigorously by Gauss in 1801 in his Disquisitiones Arithmeticae.
Once you have the prime factorizations of two or more numbers, finding GCF and LCM is straightforward. For GCF: identify all prime factors that appear in every number, and take the lowest exponent of each. For LCM: collect all prime factors that appear in any number, and take the highest exponent of each. Example with 360 = 2ยณ ร 3ยฒ ร 5 and 240 = 2โด ร 3 ร 5: GCF = 2ยณ ร 3ยน ร 5ยน =
120 (shared primes, minimum powers); LCM = 2โด ร 3ยฒ ร 5ยน = 720 (all primes, maximum powers). Enable the multi-number mode above to compute this directly. Our Common Factor Calculator also shows this step by step.
The total number of factors (also called divisors) can be calculated directly from the prime factorization. If n = pโ^aโ ร pโ^aโ ร โฆ ร pโ^aโ, then the number of factors is:
(aโ + 1) ร (aโ + 1) ร โฆ ร (aโ + 1). For 360 = 2ยณ ร 3ยฒ ร 5ยน: factors = (3+1) ร (2+1) ร (1+1) = 4 ร 3 ร 2 = 24 factors. These are all numbers from 1 to 360 that divide it evenly: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360. This calculator displays all of them in the "All Factors" section. Use our Common Factor Calculator to compare factors of multiple numbers.
A number is a perfect square if and only if every prime factor appears with an even exponent in its prime factorization. Examples: 36 = 2ยฒ ร 3ยฒ โ both exponents (2 and 2) are even โ perfect square (โ36 = 6). 100 = 2ยฒ ร 5ยฒ โ both even โ perfect square (โ100 = 10). 360 = 2ยณ ร 3ยฒ ร 5ยน โ the exponent of 2 is 3 (odd) and exponent of 5 is 1 (odd) โ NOT a perfect square. This rule also applies to perfect cubes (all exponents divisible by 3) and higher powers. The calculator shows "Perfect Square? โ/โ" based on this test. For square root operations, use our Scientific Calculator.
This calculator uses a trial division algorithm up to 999,999,999 (nearly 1 billion). Trial division works by systematically testing all primes up to โn. For n = 999,999,999, this means testing up to ~31,623 โ very fast for a modern browser. The algorithm is efficient for numbers up to about 10ยนยฒ with optimizations; beyond that, more advanced algorithms (Pollard's rho, elliptic curve factorization, general number field sieve) are needed. Factoring very large numbers (100+ digits) is computationally infeasible, which is the basis of RSA cryptography. For numbers outside the supported range, the calculator will show an error. Try 9999 or 123456 using the quick sample buttons above.