Greatest Common Divisor Calculator
The Greatest Common Divisor (GCD, also known as the Highest Common Factor, HCF) of 2 natural numbers, gcd(a,b) is the largest integral number which can be divided into both numbers a and b.
StatsFiddle currently uses 2 algorithms for determining the gcd:
Prime Factorization Method
The prime factorization technique is used when both numbers are less than 1015, and the algorithm determines the prime factors of both numbers, collects all common terms, and then multiplies these common terms out again to give the result.
For example, to determine the GCD of 24 and 36, gcd(24,36):
- 24 = 2 x 2 x 2 x 3.
- 36 = 2 x 2 x 3 x 3
- The common factors are 2 x 2 x 3, which is 12
Euclidean algorithm (Division)
The division based variant of Euclid's algorithm requires repeated application of the modulo operator to determine whether the remainder is zero, in which case, the GCD has been found.
For example, to determine gcd(54, 32)
- 54 modulo 32 = 22
- 32 modulo 22 = 10
- 22 modulo 10 = 2
- 10 modulo 2 = 0
The algorithm stops when the remainder is zero, i.e. gcd(54, 32) = 2