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

` /**`

* Return the greatest common divisor

*/

**public static ****long **gcd(**long **a, **long **b) {

**if **(b==0)

**return **a;

**else**

**return **gcd(b, a % b);

}

## No comments:

Post a Comment