Tuesday, June 5, 2007

Q6: Lowest common denominator and Greatest common divisor

Q: find the Lowest Common Denominator(LCD) and the Greatest Common Divisor(GCD) for two given integers.

The lowest common denominator or least common denominator (abbreviated LCD) is the least common multiple of the denominators of a set of vulgar fractions.

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 without remainder.

The definitions are from Wikipedia.org

A:

public class GcdAndLcm {
// This is using Euclidean algorithm.
public static int getGreatestCommonDivisor(int a, int b){
// make sure that a is greater than b
if(b > a){
int c = a; a = b; b = c;
}

if((a % b) == 0) return b;
else if( (a % b) == 1) return 1;
else return getGreatestCommonDivisor(b, (a%b));
}

public static int getLeastCommonMultiple(int a, int b){
return (a * b / getGreatestCommonDivisor(a, b));
}

public static void main(String[] args) {
System.out.println("Greatest Common Divisor for 84 and 18 is " + GcdAndLcm.getGreatestCommonDivisor(84, 18));
System.out.println("Least Common Multiple for 84 and 18 is " + GcdAndLcm.getLeastCommonMultiple(84, 18));
}
}

result:
Greatest Common Divisor for 84 and 18 is 6
Least Common Multiple for 84 and 18 is 252

No comments: