Technical Article => Programming => Algorithm

Gcd Algorithm with JavaScript

How to find the greatest common divisor between
two integers? We may encounter this problem frequently in interviews or other
occasions.

An
efficient metho to find gcd is the Euclidean
algorithm, which
uses the division
algorithm in
combination with the observation that the gcd of two numbers also divides their
difference: divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then
divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by
6 to get a remainder of 0, which means that 6 is the gcd. Formally, it could be
written as

gcd(a,0)
= a

gcd(a,b)
= gcd(b,a mod b)

The code can be
shown below;

function gcd(a,b){

if(b==0){

return a;

}else{

return gcd(b,a%b);

}

}

#### RELATED

#### 2 COMMENTS

Someone2841 [Reply] | @ 2012-12-06 15:54:05 |

/*Code with \\ representing line breaks:*/ \\ function gcd(a,b){ \\ if(a%1!=0||b%1!=0) return -1; //Return -1 if a or b are not integers \\ while(b!=0){var c = a%b; a=b; b=c;} //The algorithm \\ return a; \\ } |

## Can you write code like this? |

By sonic0002 |

A TV program visits one game company. The programmer doesn't want to showcase his programming skills to the world. So he did this. Can you write code like this? |

Reply]