Professor Java
Your Ad Here

GCD/LCM Calculator

First Number: Second Number:
Third Number (not required):

Greatest Common Factor (GCF):
Least Common Multiplier (LCM):


public static int GCD(int a, int b){ //method signature. Takes two values and returns the GCD.
    int temp; 
    if(a==b){ //Euclidean algorithm implementation. Recursion stopping case.
    if(a<b){ //Recursion. if a<b; switch to make a>b
    return(GCD(a-b,b)); //euclidean algorithm: GCD(a,b)=GCD(a-b,b)
  public static int LCM(int a, int b){ //LCM method signature. two values; returns LCM
    return(a*b/(GCD(a,b))); //by definition, a*b=GCD(a,b)*LCM(a,b)

The java code above utilizes the Euclidean algorithm: that the GCD(a,b)=GCD(a-b,b). It also uses the fact that GCD(a,a)=a and a*b=GCD(a,b)*LCM(a,b). The GCD is found recursively: if a!=b, find GCD of the lower form, until a=b. This is guaranteed by the Euclidean algoritm. Note that the javascript implementation above provides a GCD/LCM calculator for three variables, although only three are needed to find the GCD and LCM.
Provided by site.
Your Ad Here