Prime Factorization Calculator
Find prime factors, GCF, LCM, and check if numbers are prime step-by-step. Explore the Sieve of Eratosthenes, verify answers with GCF × LCM relationships, and master divisibility rules. Perfect for GCSE and A-Level maths.
Prime Calculator
Factorize · GCF · LCM · Primality · Coprime
Select an operation, enter a number, then click Calculate
How helpful was this?
Help other students find great tools
What is a Prime Number?
A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. For example, 7 is prime because the only ways to write it as a product of positive integers are 1 × 7 and 7 × 1.
The number 1 is NOT prime — it has only one factor (itself), so it fails the “exactly two factors” requirement. This exclusion is essential for preserving the uniqueness of prime factorization.
2 is the only even prime number. Every even number greater than 2 is divisible by 2 and therefore has at least three factors (1, 2, and itself), making it composite. This makes 2 unique among primes.
Formally, a prime p satisfies: if p divides a × b, then p divides a or p divides b. This is known as Euclid's lemma and is the foundation of number theory.
The Fundamental Theorem of Arithmetic
Every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. This is the Fundamental Theorem of Arithmetic — the reason prime factorization is so powerful.
Example showing uniqueness:
360 = 2³ × 3² × 5 — this is the ONLY way to express 360 as a product of primes
This uniqueness is why we exclude 1 from the primes. If 1 were prime, we could write 360 = 1 × 2³ × 3² × 5 = 1² × 2³ × 3² × 5 = …, destroying uniqueness. The theorem underpins GCF/LCM calculations, fraction simplification, and modern cryptography.
Types of Numbers
Prime Numbers
Exactly 2 factors: 1 and itself
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Composite Numbers
More than 2 factors — can be broken into primes
4, 6, 8, 9, 10, 12, 14, 15, 16, 18
Square Numbers
n × n — have an ODD number of factors
1, 4, 9, 16, 25, 36, 49, 64, 81, 100
Cube Numbers
n × n × n — all prime exponents divisible by 3
1, 8, 27, 64, 125, 216, 343, 512
Coprime Pairs
GCF = 1 — no shared prime factors
(8, 15), (14, 25), (9, 16), (7, 12)
The Number 1
Neither prime nor composite — has exactly 1 factor
The multiplicative identity: 1 × n = n
The Sieve of Eratosthenes
The Sieve of Eratosthenes is one of the oldest known algorithms, devised by the Greek mathematician Eratosthenes around 240 BC. It efficiently finds all prime numbers up to any given limit.
How the Sieve Works
- 1.Write all numbers from 2 to your limit (e.g. 100)
- 2.Start with the smallest uncrossed number (2) — it is prime
- 3.Cross out all multiples of 2 (4, 6, 8, 10, …)
- 4.Move to the next uncrossed number (3) — it is prime
- 5.Cross out all multiples of 3 (6, 9, 12, 15, …)
- 6.Repeat until you pass √limit — all remaining uncrossed numbers are prime
Our calculator includes an interactive Sieve visualization for 1–100, shown when you use the Is Prime? operation. Try it above!
First 25 prime numbers:
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
Divisibility Rules
Divisibility rules are shortcuts that let you quickly check if a number divides evenly without performing long division. These are essential for efficient prime factorization.
| Divisor | Rule | Example |
|---|---|---|
| 2 | Last digit is even (0, 2, 4, 6, 8) | 174 → 4 is even → 174 ÷ 2 = 87 ✓ |
| 3 | Sum of digits is divisible by 3 | 123 → 1+2+3 = 6 → 6 ÷ 3 = 2 ✓ |
| 4 | Last two digits form a multiple of 4 | 312 → 12 ÷ 4 = 3 ✓ |
| 5 | Last digit is 0 or 5 | 935 → ends in 5 ✓ |
| 6 | Divisible by both 2 AND 3 | 174 → even AND 1+7+4=12 ✓ |
| 8 | Last three digits form a multiple of 8 | 1,024 → 024 ÷ 8 = 3 ✓ |
| 9 | Sum of digits is divisible by 9 | 729 → 7+2+9 = 18 → 18 ÷ 9 = 2 ✓ |
| 10 | Last digit is 0 | 250 → ends in 0 ✓ |
| 11 | Alternating sum of digits is divisible by 11 | 121 → 1−2+1 = 0 → 0 ÷ 11 = 0 ✓ |
GCF vs LCM Comparison
| Property | GCF (Greatest Common Factor) | LCM (Least Common Multiple) |
|---|---|---|
| Also known as | HCF (Highest Common Factor) | Lowest Common Multiple |
| What it means | Largest number dividing both evenly | Smallest number both divide into |
| Which primes? | Only COMMON primes | ALL primes from both numbers |
| Which exponents? | MINIMUM exponent of each prime | MAXIMUM exponent of each prime |
| Formula (2 numbers) | GCF(a,b) = product of min exponents | LCM(a,b) = product of max exponents |
| Example: 24, 36 | 2² × 3¹ = 12 | 2³ × 3² = 72 |
| Key relationship | GCF(a,b) × LCM(a,b) = a × b | 12 × 72 = 24 × 36 = 864 ✓ |
Common Mistakes to Avoid
Thinking 1 is prime
1 is neither prime nor composite — it has only 1 factor
Forgetting 2 is prime (because it's even)
2 is the only even prime — it has exactly 2 factors: 1 and 2
Confusing GCF and LCM
GCF = largest shared factor (min exponents); LCM = smallest shared multiple (max exponents)
Using MAX exponents for GCF
GCF uses MINIMUM exponents of common primes. MAX exponents is for LCM
Checking divisors all the way to n
Only need to test up to √n — if n has a factor > √n, it must also have one < √n
Forgetting to include ALL prime factors for LCM
LCM uses every prime from ALL numbers, not just the common ones
Writing 12 = 2 × 6 as "prime factorization"
6 is not prime! Continue factoring: 12 = 2 × 2 × 3 = 2² × 3
Not simplifying to index notation
Write 2 × 2 × 2 × 3 × 3 as 2³ × 3² — exams expect index form
Worked Examples
Express 360 as a product of primes
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5
Find HCF and LCM of 48 and 180
48 = 2⁴ × 3
180 = 2² × 3² × 5
HCF = 2² × 3¹ = 12(min exponents of common primes)
LCM = 2⁴ × 3² × 5 = 720(max exponents of all primes)
Check: 12 × 720 = 8,640 = 48 × 180 ✓
Prove √2 is irrational
Assume √2 = a/b where a and b are integers with no common factors (i.e. HCF(a,b) = 1).
Then 2 = a²/b², so a² = 2b².
This means a² is even, so a must be even (by prime factorization, 2 must appear).
Write a = 2k. Then (2k)² = 2b², giving 4k² = 2b², so b² = 2k².
This means b is also even — contradiction! We assumed HCF(a,b) = 1.
Therefore √2 is irrational. ∎
When do two events next coincide?
Bus A runs every 12 minutes. Bus B runs every 18 minutes. Both leave the station at 9:00 AM. When do they next leave together?
12 = 2² × 3
18 = 2 × 3²
LCM(12, 18) = 2² × 3² = 36 minutes
They next leave together at 9:36 AM.
Real-World Applications
Cryptography (RSA)
RSA encryption relies on the difficulty of factoring large numbers into primes. Multiplying two large primes is easy; reversing it is computationally infeasible — this asymmetry secures online banking, HTTPS, and digital signatures.
Music & Rhythm
Musicians use LCM to find when rhythm patterns align. A 3-beat and 4-beat pattern first coincide after LCM(3,4) = 12 beats. This principle is fundamental to polyrhythms and time signature changes in composition.
Scheduling & Planning
LCM determines when recurring events coincide. If maintenance cycles run every 6, 10, and 15 days, LCM(6,10,15) = 30 tells you all three coincide every 30 days — critical for factory maintenance planning.
Simplifying Fractions
GCF simplifies fractions to lowest terms. To simplify 48/180, compute GCF(48,180) = 12, then 48/180 = 4/15. This same principle underpins ratio simplification throughout science and engineering.
First 50 Prime Numbers
1 is NOT prime (it only has one factor), and 2 is the only even prime.
Prime numbers become less frequent as numbers get larger, but there are infinitely many of them (proved by Euclid around 300 BC). The 50th prime is 229.
Frequently Asked Questions
What is prime factorization?
Breaking down a number into a product of prime numbers. For example, 60 = 2² × 3 × 5. The Fundamental Theorem of Arithmetic guarantees every composite number has a unique prime factorization.
How do I find the GCF of two numbers?
Find the prime factorization of each number, identify common prime factors, and multiply them using the smallest exponent of each. GCF(24, 36): 24 = 2³ × 3, 36 = 2² × 3². GCF = 2² × 3 = 12.
How do I find the LCM of two numbers?
Find the prime factorization of each number, list all prime factors, and multiply using the largest exponent of each prime. LCM(24, 36) = 2³ × 3² = 72.
What is the difference between GCF and LCM?
GCF is the largest number dividing both evenly (min exponents of common primes). LCM is the smallest number both divide into evenly (max exponents of all primes). They are related by GCF × LCM = a × b.
How do I know if a number is prime?
A prime has exactly two factors: 1 and itself. Check by dividing by primes up to the square root. 1 is NOT prime, and 2 is the only even prime.
What is the Sieve of Eratosthenes?
An ancient algorithm (circa 240 BC) that finds all primes up to a limit by crossing out multiples of each prime, starting from 2. Our calculator shows an interactive sieve for 1–100.
Why is 1 not a prime number?
A prime has exactly TWO distinct factors. The number 1 has only one factor (itself). Excluding 1 preserves the uniqueness of prime factorization (Fundamental Theorem of Arithmetic).
What does coprime mean?
Two numbers are coprime (relatively prime) if their GCF is 1 — they share no common prime factors. For example, 8 and 15 are coprime. The numbers themselves don't have to be prime.
What are divisibility rules?
Shortcuts for checking divisibility: by 2 (even), by 3 (digit sum ÷ 3), by 5 (ends in 0/5), by 9 (digit sum ÷ 9), by 10 (ends in 0). These help speed up prime factorization.
Is this suitable for GCSE and A-Level?
Yes! Covers all GCSE/A-Level number theory topics including prime factorization, GCF/HCF, LCM, factor trees, index notation, the Fundamental Theorem of Arithmetic, and proof by contradiction. Works with Edexcel, AQA, and OCR syllabuses.
Explore More Free Tools
All our tools are 100% free with step-by-step learning