GCF and LCM Calculator
Enter two or more whole numbers to find their greatest common factor and least common multiple, with Euclid's algorithm and the prime factorization method worked out.
Euclidean algorithm
Prime factorization method
Common factors
How to use the GCF and LCM Calculator
- Type your numbers separated by commas or spaces, or tap an example.
- Press Calculate GCF & LCM (results also update as you type).
- Read the GCF and LCM at the top.
- Follow the Euclidean steps and the prime factorization table to see how each answer is found.
- Use the common factors list to see every number that divides all your inputs.
GCF with the Euclidean algorithm
The greatest common factor (also called GCD or HCF) is the largest number that divides every number in the list. Euclid's algorithm finds it by repeated division: replace the larger number by the remainder of dividing it by the smaller one, until the remainder is 0. The last non-zero remainder is the GCF.
Example, gcd(1071, 462): 1071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0, so the GCF is 21. For three or more numbers, apply it pairwise: gcd(a, b, c) = gcd(gcd(a, b), c).
LCM from the GCF
For two numbers, lcm(a, b) = a × b ÷ gcd(a, b). For 12 and 18: gcd = 6, so lcm = 12 × 18 ÷ 6 = 36. For more numbers, chain it: lcm(12, 18, 30) = lcm(36, 30) = 36 × 30 ÷ 6 = 180.
Prime factorization method
Write each number as a product of primes. The GCF takes each prime that appears in every number, with its lowest exponent; the LCM takes every prime that appears anywhere, with its highest exponent.
| Number | Prime factors |
|---|---|
| 12 | 2² × 3 |
| 18 | 2 × 3² |
| 30 | 2 × 3 × 5 |
| GCF | 2 × 3 = 6 |
| LCM | 2² × 3² × 5 = 180 |
Where GCF and LCM are used
- Simplifying fractions: divide top and bottom by their GCF (84/126 → divide by 42 → 2/3).
- Adding fractions: the least common denominator is the LCM of the denominators.
- Scheduling: buses every 12 and 18 minutes leave together every lcm(12, 18) = 36 minutes.
- Tiling and grouping: the largest square tile that fits a 48 × 18 floor exactly is gcd(48, 18) = 6 units.
A useful check for two numbers: gcd(a, b) × lcm(a, b) = a × b.
Frequently asked questions
What is the difference between GCF and LCM?
The GCF is the largest number that divides all the numbers evenly; the LCM is the smallest number that all of them divide into. For 12 and 18, the GCF is 6 and the LCM is 36.
Are GCF, GCD and HCF the same?
Yes. Greatest common factor, greatest common divisor and highest common factor are three names for the same thing.
How do you find the GCF of three numbers?
Find the GCF of the first two, then the GCF of that result with the third number. For 84, 126 and 210: gcd(84, 126) = 42, then gcd(42, 210) = 42.
What does it mean if the GCF is 1?
The numbers are coprime (relatively prime): they share no factor other than 1. For two coprime numbers, the LCM is simply their product, such as 8 × 9 = 72.
How do you calculate the LCM quickly?
For two numbers, divide their product by their GCF: lcm(a, b) = a × b ÷ gcd(a, b). This is much faster than listing multiples.
How large can the numbers be?
Up to 30 digits each. The Euclidean algorithm handles any size instantly; the prime factorization table is shown for numbers up to 10¹⁰.