Prime Factorization Calculator

About Prime Factorization Calculator

What Is Prime Factorisation?

Prime factorisation is writing an integer as a product of prime numbers. Every integer greater than 1 has exactly one such representation (up to ordering), which is the content of the Fundamental Theorem of Arithmetic - formally proved by Carl Friedrich Gauss in his 1801 Disquisitiones Arithmeticae, though the result appears in Euclid's Elements (Book IX, Proposition 14, c. 300 BCE).

Worked example: Factorise 360

1. 360 ÷ 2 = 180
2. 180 ÷ 2 = 90
3. 90 ÷ 2 = 45
4. 45 ÷ 3 = 15
5. 15 ÷ 3 = 5
6. 5 is prime - done
7. 360 = 2³ × 3² × 5

Prime Factorisation Reference

Number	Prime Factorisation	Number of Divisors
12	2² × 3	6
24	2³ × 3	8
36	2² × 3²	9
60	2² × 3 × 5	12
100	2² × 5²	9
120	2³ × 3 × 5	16
180	2² × 3² × 5	18
360	2³ × 3² × 5	24
1000	2³ × 5³	16
2520	2³ × 3² × 5 × 7	48

The Factor Tree

A factor tree shows the stepwise decomposition of a number into two smaller factors at each branch until every leaf is prime. For numbers up to 100,000, this calculator draws an SVG factor tree. Starting from your number at the top, each branch shows a division into two factors. Prime factors are highlighted in coloured circles.

There is no single "correct" factor tree. You can start by dividing by 2, or by any factor you spot. All valid trees produce the same prime factorisation - that is what the Fundamental Theorem guarantees. Factor trees are the most commonly taught method in UK Key Stage 2-3 maths (National Curriculum topic 6N4) and in US Common Core grade 6 (6.NS.B.4).

How to Count Divisors from Prime Factorisation

The total count of divisors is the product of each exponent plus one. If a number has the factorisation p₁^a × p₂^b × p₃^c, then:

Number of divisors = (a+1) × (b+1) × (c+1)

This works because each divisor is formed by choosing an exponent between 0 and a for p₁, between 0 and b for p₂, and so on - giving (a+1)(b+1)(c+1) combinations.

Example: 360 = 2³ × 3² × 5¹

• Number of divisors = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24
• The 24 divisors: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360

How Do You Check If a Number Is Prime?

A number n is prime if it has no divisors other than 1 and itself, which you can verify by testing only candidate divisors up to √n. Every composite number has a factor at or below its square root, so if none of 2, 3, ..., ⌊√n⌋ divide n, then n is prime. This reduces an O(n) scan to O(√n) - for n = 10¹², only about one million candidates.

The first 25 primes (all primes below 100): 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.

The Prime Number Theorem, proved independently by Jacques Hadamard and Charles-Jean de la Vallée Poussin in 1896, states that the number of primes below x is approximately x / ln(x). For x = 1 billion, this predicts about 48.3 million primes - the actual count is 50,847,534. Primes become rarer, but they never run out: Euclid's proof (c. 300 BCE) shows there are infinitely many.

Why Prime Factorisation Matters

Prime factorisation is foundational to number theory and appears in cryptography, hashing, coding theory, and basic fraction arithmetic. The table below maps common applications.

Application	How Primes Are Used
Simplifying fractions	Cancel common prime factors in numerator and denominator
Finding GCF	Take minimum power of shared primes
Finding LCM	Take maximum power of all primes
RSA encryption	Security relies on difficulty of factoring large numbers
Hash functions	Prime-sized hash tables reduce collisions
Music theory	Tuning systems based on ratios of small primes
Error-correcting codes	Reed-Solomon codes use prime-field arithmetic
Cycle detection	LCM of cycle lengths finds synchronisation period

GCD and LCM from Prime Factors

The greatest common divisor is the product of shared primes raised to the lowest shared exponent, and the least common multiple is the product of every prime involved raised to the highest exponent.

Example: Find GCD and LCM of 48 and 180

• 48 = 2⁴ × 3
• 180 = 2² × 3² × 5
• GCD: take minimum powers of shared primes = 2² × 3 = 12
• LCM: take maximum powers of all primes = 2⁴ × 3² × 5 = 720
• Check: GCD × LCM = 12 × 720 = 8,640 = 48 × 180 ✓

The identity GCD(a, b) × LCM(a, b) = a × b holds for any pair of positive integers, and lets you compute LCM quickly once you have the GCD. The calculator above uses the Euclidean algorithm (Euclid's Elements, Book VII, Proposition 2) for GCD because it avoids factorising both numbers - an important distinction when the inputs are large.

What Are Some Interesting Prime Patterns?

Primes show up in several well-known patterns that are worth recognising when you work with factorisations. Twin primes are pairs that differ by 2 (3 and 5, 11 and 13, 29 and 31) - the Twin Prime Conjecture, that there are infinitely many, is still unproved, though Yitang Zhang proved in 2013 that there are infinitely many pairs of primes differing by at most 70 million, later tightened by the Polymath8 collaboration to 246.

Mersenne primes have the form 2^p - 1 where p is itself prime. The largest known prime as of late 2024 is 2^136,279,841 - 1, discovered by Luke Durant on 12 October 2024 in the GIMPS distributed-computing project - a number with 41,024,320 decimal digits (source: Great Internet Mersenne Prime Search).

Goldbach's conjecture (1742) says every even number greater than 2 is the sum of two primes. It has been verified computationally up to 4 × 10¹⁸ but remains unproved.

Why Is Factoring Large Numbers Hard?

Trial division is fast for numbers up to about 10¹² but becomes impractical for 100-digit numbers. RSA public-key cryptography, published by Rivest, Shamir, and Adleman in 1978, depends on this asymmetry: multiplying two large primes is fast, but factoring the product is not. The current RSA factoring record is RSA-250 (829 bits, 250 decimal digits), factored in February 2020 by Boudot et al. using about 2,700 CPU-core-years on a cluster (source: cado-nfs team announcement).

Typical RSA keys today are 2,048 bits (617 decimal digits) or 3,072 bits, which are estimated to be trillions of times harder to factor with classical hardware. Shor's quantum algorithm (Peter Shor, 1994) would factor these in polynomial time on a fault-tolerant quantum computer, which is why NIST selected post-quantum lattice schemes (ML-KEM, ML-DSA) as drawn-up standards in August 2024.

How Fast Is Trial Division?

Trial division tests candidate divisors 2, 3, 5, 7, ... up to √n and is the method this calculator uses. For n up to 10¹² this runs in a fraction of a second in a modern browser - roughly 10⁶ iterations of a tight integer loop, which a JavaScript engine like V8 clears in 10-30 milliseconds. Beyond 10¹⁵ the approach slows noticeably, and serious number theory libraries switch to more advanced algorithms.

Algorithm	Typical Use	Best Range
Trial division	Classroom, small integers	up to ~10¹²
Pollard's rho (1975)	Fast small-factor extraction	up to ~10²⁵
Elliptic Curve Method (ECM)	Medium composites with small factors	up to ~10⁵⁰
Quadratic Sieve (QS)	Semiprimes ~100 digits	up to ~10¹⁰⁰
General Number Field Sieve (GNFS)	Large semiprimes, RSA research	10¹⁰⁰ and above

For primality testing specifically (deciding whether a number is prime without necessarily factoring it), the AKS algorithm (Agrawal, Kayal, Saxena, 2002) runs in polynomial time and was the first proven deterministic polynomial-time primality test. In practice, probabilistic tests like Miller-Rabin are much faster and are what libraries like OpenSSL use when generating RSA keys.

Common Mistakes Students Make

• Forgetting that 1 is not prime. The convention that 1 is not prime keeps the Fundamental Theorem clean - otherwise factorisations would not be unique.
• Including 1 in the divisor count rule. (a+1)(b+1)(c+1) already counts 1 (every exponent chosen as 0) and n itself (every exponent maxed out). Do not add or subtract anything.
• Stopping trial division too early. After dividing out a factor, the remaining number may still have larger prime factors. Only stop when the candidate divisor exceeds √(remaining).
• Confusing GCF and LCM. Use GCF to simplify a single fraction, LCM to add fractions with unlike denominators. The fraction calculator does this automatically.
• Assuming all primes are odd. 2 is the only even prime. All others are odd because any even number has 2 as a factor.

For dedicated GCF and LCM calculations on more than two numbers, the GCF and LCM calculator handles up to 10 inputs at once. For fraction arithmetic that relies on these values, the fraction calculator simplifies automatically using internal GCD logic. For step-by-step algebra built on these same integer tools, try the equation solver.

All computation runs in your browser. No data is sent to any server.

Sources

• Wolfram MathWorld - Fundamental Theorem of Arithmetic
• Wolfram MathWorld - Prime Number Theorem
• OEIS A000040 - The prime numbers
• GOV.UK - National Curriculum in England: Mathematics Programmes of Study
• NIST - Post-Quantum Cryptography Standardisation
• Encyclopaedia Britannica - Prime Factorisation