In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers.

The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The code below shows how to implement gcd function recursively.

/** * Return the greatest common divisor */ public static long gcd(long a, long b) { if (b==0) return a; else return gcd(b, a % b); } |