Prime Factorization Calculator
Find the prime factorization of any positive integer instantly. Shows the complete factor tree, product of primes notation, exponential form, and divisibility steps. Also calculates HCF and LCM for two numbers. Aligned with UK GCSE Maths (Edexcel, AQA, OCR).
Optionally, enter a second number to find HCF and LCM:
First 25 Prime Numbers
| # | Prime | # | Prime | # | Prime | # | Prime | # | Prime |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 2 | 3 | 3 | 5 | 4 | 7 | 5 | 11 |
| 6 | 13 | 7 | 17 | 8 | 19 | 9 | 23 | 10 | 29 |
| 11 | 31 | 12 | 37 | 13 | 41 | 14 | 43 | 15 | 47 |
| 16 | 53 | 17 | 59 | 18 | 61 | 19 | 67 | 20 | 71 |
| 21 | 73 | 22 | 79 | 23 | 83 | 24 | 89 | 25 | 97 |
What Is Prime Factorization?
Prime factorization (also called prime decomposition or expressing a number as a product of its prime factors) is the process of writing any positive integer as a multiplication of prime numbers. This is a core topic at GCSE level in England, appearing on Edexcel, AQA, and OCR papers, and underpins many other topics including HCF, LCM, and number theory.
For example: 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5
The Fundamental Theorem of Arithmetic guarantees that this decomposition is unique for every integer greater than 1 — there is only one way to write any number as a product of primes (ignoring the order of factors).
What Is a Prime Number?
A prime number is a positive integer greater than 1 with exactly two factors: 1 and itself. The sequence of prime numbers begins: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37…
Key facts tested at GCSE:
- 2 is the only even prime number. All other even numbers are divisible by 2, so they are composite.
- 1 is NOT prime. It has only one factor (itself), not two.
- There are infinitely many prime numbers — proved by Euclid around 300 BC.
- There is no largest prime. As of 2024, the largest known prime has over 41 million digits.
How to Find Prime Factorization: Division Method
The division method (also called the ladder method or repeated division) is the most systematic approach used in UK GCSE maths:
- Start with the smallest prime (2). Divide your number by 2 as many times as possible.
- Move to the next prime (3) and divide as many times as possible.
- Continue with 5, 7, 11… until the result is 1.
Example: Prime factorization of 180
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
180 = 2² × 3² × 5
How to Draw a Factor Tree
A factor tree is a visual method that works by repeatedly splitting a number into any two factors until all branches end in prime numbers:
- Write your number at the top (e.g., 60).
- Split into any two factors (e.g., 60 = 6 × 10). These become branches.
- If a factor is not prime, split it further (6 = 2 × 3; 10 = 2 × 5).
- Circle all prime numbers where the branches end (2, 3, 2, 5).
- Write the product: 60 = 2 × 3 × 2 × 5 = 2² × 3 × 5.
Note: Different starting splits give different-looking trees, but always the same final prime factorization — confirming the Fundamental Theorem of Arithmetic.
Using Prime Factorization to Find the HCF
The Highest Common Factor (HCF) — also called the Greatest Common Divisor (GCD) — is the largest number that divides exactly into two (or more) given numbers.
Example: HCF(36, 48). 36 = 2² × 3² 48 = 2&sup4 × 3 HCF = 2² × 3 = 12
Real-world application: HCF is used when cutting ribbons into equal lengths, sharing items into equal groups, or simplifying fractions. In the UK, GCSE problems often ask students to find the HCF to determine the maximum equal group size.
Using Prime Factorization to Find the LCM
The Lowest Common Multiple (LCM) is the smallest positive integer that is divisible by two (or more) given numbers.
Example: LCM(12, 18). 12 = 2² × 3 18 = 2 × 3² LCM = 2² × 3² = 36
Real-world application: LCM is used for finding when two cyclic events coincide again (e.g., two buses with different frequencies both starting at the same time — when do they next depart together?). LCM is also used for adding fractions with different denominators.
HCF × LCM Identity
For any two positive integers a and b, the following identity always holds:
This provides a useful check: after finding HCF and LCM, verify that their product equals the product of the original numbers.
GCSE Exam-Style Questions
| Number | Prime Factorization | Exponential Form |
|---|---|---|
| 12 | 2 × 2 × 3 | 2² × 3 |
| 24 | 2 × 2 × 2 × 3 | 2³ × 3 |
| 36 | 2 × 2 × 3 × 3 | 2² × 3² |
| 60 | 2 × 2 × 3 × 5 | 2² × 3 × 5 |
| 100 | 2 × 2 × 5 × 5 | 2² × 5² |
| 120 | 2 × 2 × 2 × 3 × 5 | 2³ × 3 × 5 |
| 360 | 2 × 2 × 2 × 3 × 3 × 5 | 2³ × 3² × 5 |
| 1000 | 2 × 2 × 2 × 5 × 5 × 5 | 2³ × 5³ |
Prime Numbers in Cryptography
Prime numbers are the foundation of modern internet security. The RSA algorithm, used to secure online banking, e-commerce, and HTTPS connections across the UK and worldwide, relies on the following mathematical fact:
It is easy to multiply two large prime numbers together, but computationally infeasible to factorise the result back into primes when the primes are sufficiently large (hundreds of digits). This one-way difficulty is the basis of public-key cryptography.
When you see a padlock icon in your browser visiting a UK bank website, the security of that connection depends on prime factorization being hard for very large numbers.
The Sieve of Eratosthenes
The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit, devised by the Greek mathematician Eratosthenes around 240 BC:
- Write all numbers from 2 to the target limit.
- Start with p = 2 (the first prime). Mark all multiples of 2 as composite (4, 6, 8…).
- Move to the next unmarked number (3). Mark all multiples of 3 (6, 9, 12…).
- Repeat for each unmarked number. If p² exceeds the limit, all remaining unmarked numbers are prime.
The sieve runs in O(n log log n) time and remains the most efficient simple algorithm for generating small primes. It is studied in computer science A-Level and university discrete mathematics.
Frequently Asked Questions
What is prime factorization?
Expressing a number as a product of its prime factors. Every integer greater than 1 has a unique prime factorization (Fundamental Theorem of Arithmetic). Example: 60 = 2² × 3 × 5.
What is a prime number?
A positive integer greater than 1 with exactly two factors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13. Note: 1 is NOT prime; 2 is the only even prime.
How do I draw a factor tree?
Write the number at the top, split into any two factors, then keep splitting non-prime branches until all ends are prime. Collect all the primes at the branch tips for the factorization.
How do I find the HCF using prime factorization?
Write out the prime factorization of both numbers. Identify shared primes and take the lower power of each. Multiply these together to get the HCF.
How do I find the LCM using prime factorization?
Write out both prime factorizations. Take all primes that appear in either number, using the higher power. Multiply together for the LCM.
Is 1 a prime number?
No. 1 has only one factor (itself), not two. By definition, primes must have exactly two distinct factors. 1 is neither prime nor composite.
What is the Fundamental Theorem of Arithmetic?
Every integer greater than 1 has a unique prime factorization. This means there is only one way to express any number as a product of primes (order does not matter). This uniqueness is why prime factorization is so powerful in mathematics.