GCD & LCM Formulas: Euclidean Algorithm and Factor Count

Contents
1. Counting Factors and the Prime Factorization Formula
Checking every factor of a huge number one by one takes a lot of computing resources and time. Number theory gets around this quickly with the prime factorization formula.
Formula for the number of factors: When a natural number N is prime factorized as follows,
N = a^p × b^q × c^r × …(Here a, b, and c are distinct primes, and p, q, and r are positive integer exponents.)
Total number of factors = (p + 1) × (q + 1) × (r + 1) × …Worked example (finding the number of factors of 72):
- Prime factorization: 72 = 8 × 9 = 2^3 × 3^2
- Plug in the exponents: p = 3, q = 2
- Number of factors: (3 + 1) × (2 + 1) = 4 × 3 = 12 What this means: Without counting the factors of 72 on your fingers, the formula confirms there are 12 in total (
1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72).
2. The Euclidean Algorithm and the GCD and LCM Formulas
A classic programming algorithm for efficiently finding the greatest common divisor of two natural numbers is the Euclidean algorithm, established around 300 BCE.
Recursive Formula for the Euclidean Algorithm
Given two numbers a and b (a > b), let r be the remainder when a is divided by b. The following identity holds.
GCD(a, b) = GCD(b, r)
The divisor at the point when the remainder becomes 0 is the final greatest common divisor of the two numbers.
- Example (finding GCD(120, 36)):
- 120 ÷ 36 = 3, remainder 12 → GCD(120, 36) = GCD(36, 12)
- 36 ÷ 12 = 3, remainder 0 → Since the remainder is 0, the last divisor, 12, is the final greatest common divisor.
Least Common Multiple Formula
Once you know the greatest common divisor (GCD), you can get the least common multiple (LCM) immediately with the proportional identity below.
LCM(a, b) = (a × b) ÷ GCD(a, b)
How to Use the Factors, GCF & LCM Calculator
If factoring multi-digit numbers by hand or repeating the Euclidean division loop sounds tedious, try a dedicated number theory calculator.
Free · no sign-up · enter two numbers to get the factor list, GCD, and LCM instantly

The tool's workflow is very clear.
- Enter the numbers: Enter the two natural numbers you want to calculate in the Number A and Number B fields (range: 1 to 10,000,000).
- As soon as you type, the detailed analysis area shows the factor list for A and B, the list of common factors, and the prime factorization results.
- At the same time, the greatest common divisor (GCD) and least common multiple (LCM) values appear in bold highlight cards at the top, along with the step-by-step calculation using prime factors.
Summary
Factors, greatest common divisors, and least common multiples may look like basic arithmetic, but they are essential calculations that form the backbone of the digital world: the four operations with fractions, bit operations in computer number systems, and key encryption in information security. Manual calculations with multi-digit numbers are prone to error, so checking your work against the calculator's Euclidean algorithm results lets you spot numerical errors quickly.
Free · no sign-up · enter two numbers to get the factor list, GCD, and LCM instantly
Frequently Asked Questions
What do you call two natural numbers whose greatest common divisor is 1, and why does it matter?
When two numbers have no common divisor other than 1, mathematicians call them relatively prime (or coprime).
- Coprimality is the key benchmark for reducing a fraction to lowest terms when it cannot be reduced any further.
- In computer cryptography (RSA), in particular, you pick two large primes, multiply them to get n, and use an integer that is relatively prime to a value derived from n when generating the public key. Judging whether numbers are coprime is a basic prerequisite of the key-generation process.
How do you find the greatest common divisor and least common multiple of three or more numbers (say, A, B, and C)?
This calculator takes two numbers at a time, so for three or more numbers you work through them in pairs and carry the result forward.
Extending the GCD formula:
GCD(A, B, C) = GCD(GCD(A, B), C)(In other words, enter A and B first to get their greatest common divisor, then enter that result and C to get the greatest common divisor of all three numbers.)
Extending the LCM formula:
LCM(A, B, C) = LCM(LCM(A, B), C)Use the same approach: find the LCM of A and B first, then enter that value with C. You can extend this process one number at a time no matter how many numbers you have.
This article is for informational purposes and references standard number theory, including the Euclidean algorithm.
This article was adapted from our Korean original. Read the Korean original