GCF and LCM Calculator
Find the greatest common factor and least common multiple of two to twenty whole numbers, worked by Euclid's algorithm and by prime factorization.
The interactive tool loads here when JavaScript runs.
About this toolWhat is the GCF and LCM Calculator?
Enter two or more whole numbers separated by commas or spaces and get their greatest common factor (also called the greatest common divisor, GCD, or highest common factor, HCF) and their least common multiple. Both are shown with two independent methods so you can follow whichever your course uses.
The first method is Euclid's algorithm: divide, keep the remainder, and repeat until the remainder is zero. Each line is shown as a = q × b + r. The second is prime factorization: a table lists the power of each prime in each number, the GCF takes the lowest power of every shared prime and the LCM takes the highest power of every prime that appears.
Numbers can be large (up to 30 digits each), because the arithmetic uses exact big integers. For small results the list of all common factors is printed too.
- GCF (GCD, HCF) and LCM of up to 20 numbers
- Euclid's algorithm written line by line
- Prime factorization table with exponents
- List of all common factors for small results
- Exact big-integer arithmetic up to 30 digits
How to use the GCF and LCM Calculator
- Type the numbers in the box, separated by commas or spaces, for example 12, 18, 30.
- Read the GCF and LCM at the top of the results.
- Follow Method 1 for Euclid's algorithm, one division per line, for each pair.
- Follow Method 2 for the prime factorization table and the lowest-power and highest-power rule.
- Copy the result or share a link to the same list.
Worked examples
Three numbers
Input
12, 18, 30
Output
GCF 6, LCM 180
12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5. Lowest shared powers give 2 × 3 = 6; highest powers give 2² × 3² × 5 = 180.
Euclid's classic
Input
1071, 462
Output
GCF 21, LCM 23,562
1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0. The last non-zero remainder is 21, and 1071 × 462 / 21 = 23,562.
Common denominator
Input
4, 6, 8, 10
Output
LCM 120
To add quarters, sixths, eighths and tenths, 120 is the smallest denominator they all share.
Background and insight
Euclid described the algorithm in Book VII of the Elements, around 300 BC, and it is still the method computers use. It rests on one fact: any number that divides both a and b also divides the remainder of a ÷ b. So GCF(1071, 462) = GCF(462, 147) = GCF(147, 21) = 21, reached in three divisions. The number of steps grows only with the number of digits, which is why it works instantly on numbers far too big to factor.
The LCM follows from the GCF. For two numbers, GCF × LCM = a × b, so LCM = a × b / GCF. For a longer list, both are built up a pair at a time: GCF(a, b, c) = GCF(GCF(a, b), c), and the same for the LCM. The product identity does not hold for three or more numbers, which is a common exam trap.
Edge cases follow the usual conventions. GCF(0, n) is n, because every number divides 0. The LCM of a list containing 0 is 0. GCF(0, 0) is left undefined here. Negative inputs are treated by their absolute value, since factors and multiples are normally quoted as positive numbers.
Common use cases
Fractions
Use the LCM as the lowest common denominator when adding fractions, and the GCF to reduce a fraction to lowest terms.
Scheduling and cycles
Two buses every 12 and 18 minutes leave together again after LCM = 36 minutes; gears with 30 and 45 teeth realign after LCM ÷ teeth turns.
Cutting and tiling
The GCF of a 240 cm by 180 cm floor (60 cm) is the largest square tile that fits with no cuts.
Programming
Check gcd and lcm functions, or work out loop periods and buffer alignments, with exact big-integer answers.
Tips and limitations
- If the GCF is 1 the numbers are coprime: they share no prime factor, though neither has to be prime itself (8 and 15).
- For exactly two numbers, check your work with GCF × LCM = a × b. For three or more, that shortcut is wrong.
- Euclid's method is quicker by hand for large numbers; the prime factor method is quicker to read when the numbers are small and have obvious factors.
- The LCM of numbers 1 to 10 is 2,520 and of 1 to 20 is 232,792,560, which shows how fast LCMs grow.
- Spaces, commas and semicolons all separate numbers, so you can paste a column from a spreadsheet.
Frequently asked questions
What is the difference between GCF and LCM?
The GCF is the largest number that divides every number in the list. The LCM is the smallest positive number that every number in the list divides into. For 8 and 12, the GCF is 4 and the LCM is 24.
Are GCF, GCD and HCF the same thing?
Yes. Greatest common factor, greatest common divisor and highest common factor are three names for the same number. GCD is common in programming and higher maths, HCF in British schools.
How does Euclid's algorithm find the GCF?
Divide the larger number by the smaller and keep the remainder. Replace the larger number with the smaller and the smaller with the remainder, and repeat. When the remainder reaches 0, the last divisor is the GCF.
How do I find the LCM using prime factorization?
Factor each number into primes and take every prime that appears, raised to the highest power found in any of the numbers. For 12 = 2² × 3 and 18 = 2 × 3², the LCM is 2² × 3² = 36.
What is the GCF of two prime numbers?
It is 1, because a prime has no factors other than 1 and itself. Their LCM is simply their product: for 7 and 11, the LCM is 77.
Can I find the GCF of more than two numbers?
Yes. Combine them a pair at a time: GCF(12, 18, 30) = GCF(GCF(12, 18), 30) = GCF(6, 30) = 6. This tool accepts up to 20 numbers and shows each pairwise step.
Is there an in-depth guide to the GCF and LCM Calculator?
Yes. “Percentages, Fractions and Ratios: How the Arithmetic Fits Together” covers the background, how it works, common pitfalls and worked examples. Read the full guide.
Related Tools You May Like
Free, in-browser tools that pair well with this one.