Euclidean algorithm, greatest common divisor (GCD), highest common factor (HCF)

This javascript calculator calculates for you the Greatest Common Divisor.

GCD( , ) =

Examples:
GCD(1071,1029)=21
GCD(35,42)=7

The Euclidean algorithm

function eucledian(a,b){ // a and b must be postive integers, calculates GCD
 if (a ==0){
 return(b);
 }
 while(b > 0){
 if (a > b) {
 a = a - b;
 }else{
 b = b - a;
 }
 }
 return(a);
}

The following algorithm is a modified version of the original Euclidean algorithm. It requires fewer iterations to come to the result.

function eucledian_mod(a,b){ // a and b must be postive integers, calculates GCD
 while(a > 0 && b > 0){
 if (a > b) {
 a = a % b; // a modulo b
 }else{
 b = b % a;
 }
 }
 return(a+b); // either a or b is zero
}

Least Common Multiple (LCM) also called the lowest common multiple or smallest common multiple

The LCM can be calculated using the GCD:

LCM(a,b)=abs(a*b)/GCD(a,b)
abs(a*b) is the absolute of a times b, (always a positive number)

Calculate the LCM

LCM( , ) =

References

• http://en.wikipedia.org/wiki/Euclidean_algorithm

This page is operting system independent. It only requires a javascript capable webbrowser. You can install it locally on your PC, iPhone, Android-phone or netbook just by saving this page on the desktop. The page is optimized for mobile devices.

© Guido Socher, License: GPL, This software is provided without warrenty of any kind.
Version: 2012年12月22日