通过

Greatest Common Divisor (and Lowest Common Multiple)

  • 项目

It's worth repeating the wikipedia definition for GCD here, as it's explains it well: "The greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. (See their full explanation here).

Euclid's algorithm to derive the GCD is simple and fast, and easily implemented in code as:

 

  static int GetGCD(int num1, int num2)
 {
 //check for valid inputs
 if (num1 < 1 || num2 < 1)
 {
 return -1;
 }
 
 while (num1 != num2)
 {
 if (num1 > num2)
 {
 num1 = num1 - num2;
 }
 if (num2 > num1)
 {
 num2 = num2 - num1;
 }
 }
 return num1;  

In this approach the greater number decreases by the difference each time until they equal each other (at which point there woult also be no remainder from a modulus operation between them). This lower, equal number is the GCD. In some implementations you might see an "else" clause between the two "if" statements, but leaving it out as is done here allows for two reduction operations to happen between loop tests. You can do the same by applying the modulus operand to the two numbers swapping the results each time as you re-enter the loop. It's all about getting the remainder to equal 0. We can do this with recursion as seen here:

 

  public static int RecursiveGCD(int num1, int num2)
 {
 if (num2 == 0)
 {
 return num1;
 }
 else
 {
 return RecursiveGCD(num2, num1 % num2);
 }
 }

This second example has no handling for zero values, and while it won't crash it will give results for zeroes or minus numbers. One way of bullet-proofing this would be to have two methods - one which performs the valid inputs check, and then just calls the recursive method.

 Lowest (or least) common multiple

Again using the Wikipidea definition: "The least common multiple (also called the lowest common multiple or smallest common multiple) of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b.[1] If either a or b is 0, LCM(a, b) is defined to be zero.

 

So I can't remember if this was also a Euclides formula, but dividing the product of the two numbers by their greatest common divisor gives the smallest possible common product of these two numbers individually multiplied with another, as follows:

  static int GetLCM(int num1, int num2)
 {
 return (num1 * num2) / GetGCD(num1, num2);
 }

Comments

  • Anonymous
    March 04, 2013
    //check for valid inputs if (num2 < 1 || num2 < 1) Should be //check for valid inputs if (num1 < 1 || num2 < 1)

  • Anonymous
    March 04, 2013
    Thanks Rc - fixed now!