Find the GCF (GCD) of any set of positive integers — using the Euclidean algorithm and prime factorisation, with the corresponding LCM.
Results update live as you type.
Greatest Common Factor
LCM
144
least common multiple
Product
1,728
a × b = GCF × LCM
Coprime?
No
GCF > 1
Simplified ratio
4 : 3
a/GCF : b/GCF
Multi-number GCF
6
12, 18, 24, 36
Multi-number LCM
72
least common multiple
Euclidean steps
2
divisions needed
Prime overlap
2² × 3
shared factorisation
| Term | Definition | Notes |
|---|---|---|
| GCF | Largest integer that divides all inputs | aka GCD, HCF |
| LCM | Smallest integer divisible by all inputs | aka LCD |
| Coprime | GCF equals 1 (no common factor > 1) | e.g. 14, 15 |
| Euclidean | gcd(a, b) = gcd(b, a mod b) | O(log n) |
| Identity | GCF × LCM = a × b | for any pair |
The Method
Two complementary algorithms are used. Euclid's algorithm repeatedly replaces the pair (a, b) with (b, a mod b) until the remainder is zero — the last non-zero remainder is the GCF. It is over 2300 years old and runs in O(log min(a, b)) time, which means even huge inputs finish in microseconds. The prime factorisation method writes both numbers as products of primes, then for each prime takes the minimum power — more intuitive but much slower for large numbers.
Euclidean working — gcd(48, 36)
About This Tool
A Greatest Common Factor (GCF) calculator — also called a GCD calculator (Greatest Common Divisor) or HCF calculator (Highest Common Factor) — finds the largest positive integer that divides each of two or more numbers exactly. Enter two numbers, or a comma-separated list of any length, and the calculator returns the GCF, the corresponding LCM, the full Euclidean working, and a side-by-side prime factorisation comparison.
The GCF is one of the most useful concepts in elementary number theory. It is the engine behind simplifying fractions (divide top and bottom by their GCF), reducing ratios (divide both terms by their GCF), and finding common denominators (via the LCM, which is computed using the GCF). The extended Euclidean algorithm generalises this to find modular inverses, which is foundational in RSA cryptography and other public-key systems.
This calculator uses Euclid's algorithm — over 2300 years old and still the gold standard — to compute the GCF in O(log min(a, b)) divisions. Even for numbers in the billions it finishes in microseconds. The prime factorisation method is shown alongside for educational comparison; both produce the same answer but the Euclidean is dramatically faster for large inputs. All computation runs entirely in your browser using IEEE 754 double-precision arithmetic — exact for integers up to 2⁵³ − 1.
Use this free GCF calculator for homework, exam revision, simplifying fractions and ratios, or as a teaching aid. The Euclidean working is shown step-by-step exactly as you would write it out by hand. No sign-up, no tracking, no data sent to any server.
Two & Many Inputs
GCF of a pair or any comma-separated list — both shown side by side.
Euclidean Working
Every division step of Euclid's algorithm, exactly as written by hand.
Prime Factor Compare
Side-by-side prime factorisations with the shared "GCF row" highlighted.
LCM Bonus
LCM derived for free via the GCF × LCM = a × b identity.
100% Free & Private
No account, no tracking — every calculation runs locally in your browser.
Simplified Ratio
The pair reduced to lowest-terms ratio — same step that simplifies fractions.
Two or more numbers, one click, and a full working is laid out for you.
Type any positive integer into the "Number A" field — this is the first input to the pairwise GCF.
Type the second positive integer. The GCF of the pair appears immediately at the top of the summary card.
Use the multiple numbers field for a comma-separated list of any length — the calculator reduces them pairwise to find the multi-number GCF and LCM.
The prime factor table shows the prime factorisation of each input side by side. The minimum power in each column gives the GCF row (highlighted).
The formula card shows the step-by-step Euclidean working: each line is gcd(a, b) = gcd(b, a mod b), repeated until the remainder is zero.
Hit Copy for a clean text summary — or Share to send the link straight to a friend or paste into a report.
Everything you need to know about GCF, GCD, HCF, Euclidean algorithm, and how to interpret your result.
The Greatest Common Factor (GCF) of two or more positive integers — also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) — is the largest positive integer that divides each number exactly. For example, GCF(48, 36) = 12: both 48 and 36 are divisible by 12, and no larger number divides both.
None — they are three names for the same thing. GCF (Greatest Common Factor) is the everyday US name; HCF (Highest Common Factor) is the standard UK and Commonwealth name; GCD (Greatest Common Divisor) is the formal mathematical name and the one used in computer science (e.g. Python's math.gcd). They always produce the same number for the same inputs.
GCF is the largest number that divides both inputs. LCM (Least Common Multiple) is the smallest number that both inputs divide. They are linked by the identity GCF(a, b) × LCM(a, b) = a × b — so knowing one immediately gives you the other. For 48 and 36: GCF = 12, LCM = 144, and 12 × 144 = 1728 = 48 × 36. ✓
Euclid's algorithm uses the identity gcd(a, b) = gcd(b, a mod b). Repeatedly replace the larger number with the remainder until the remainder is zero — the last non-zero remainder is the GCF. Example: gcd(48, 36) → gcd(36, 12) → gcd(12, 0) = 12. It is one of the oldest non-trivial algorithms in mathematics (Euclid c. 300 BC) and runs in O(log min(a, b)) divisions — fast even for billion-digit inputs.
Find the prime factorisation of each number, then for each prime take the minimum power that appears in all factorisations. The product of those is the GCF. For example 48 = 2⁴ × 3, 36 = 2² × 3² → GCF = 2² × 3 = 12. It is more visual and pedagogically useful than the Euclidean algorithm but much slower for large numbers (factoring is itself an open hard problem at RSA scales).
Yes. The GCF is associative: GCF(a, b, c) = GCF(GCF(a, b), c). So you can find the GCF of a list by computing pairwise GCFs in any order. The multi-number field in this calculator does exactly that — it takes the GCF of the first two, then folds in the next number, and so on. The same trick works for LCM.
Two numbers are coprime (also called relatively prime) if their GCF is 1 — they share no common factor greater than 1. So 14 and 15 are coprime (GCF = 1), but 14 and 21 are not (GCF = 7). Note that being coprime doesn't require either number to itself be prime: 8 and 15 are coprime even though neither is prime. Coprimality is the foundation of modular inverses and the security of RSA.
Most commonly: simplifying fractions (divide both numerator and denominator by their GCF — that's how 12/18 becomes 2/3, with GCF 6), reducing ratios (8 : 12 becomes 2 : 3, GCF 4), and finding common denominators (via LCM, which is computed using GCF). The extended Euclidean algorithm generalises this to find modular inverses and is foundational in RSA cryptography and other public-key systems.
Related but distinct. Factoring finds all factors (or prime factors) of a single number; GCF finds the largest factor shared by two or more numbers. The factor calculator (see related tools) is what you want for a single number; the GCF calculator is what you want when comparing two or more.
No. The GCF must divide every input, so it is always at most as large as the smallest input. It is equal to the smallest input precisely when the smallest input divides all the others: GCF(6, 12, 18) = 6, because 6 divides both 12 and 18.
The calculator uses IEEE 754 double-precision arithmetic and is exact for integers up to 2⁵³ − 1 ≈ 9 × 10¹⁵ (about 9 quadrillion). The Euclidean algorithm itself is O(log min(a, b)), so even at that scale you get an answer in microseconds. For arbitrary-precision integers (RSA-scale, 100+ digits) you need a big-integer library such as Python's int or JavaScript's BigInt.
Each step at least halves the larger number — that's why it runs in O(log n) divisions. Lamé proved (1844) that the worst case is consecutive Fibonacci numbers, and even then it finishes in about 1.44 × log₂(n) steps. For 64-bit numbers that's at most about 92 steps. The constant factor is tiny — modern hardware does each step in a single CPU instruction.