DM42 program: Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

The LCM is useful for finding a common denominator for adding fractions.
The GCD of two integers is the greatest common factor number that divides them without rest.

Start a new program with: GTO . . PRGM

DM42 code:

00 { 20-Byte Prgm }
01 LBL "GCD"
02 X>Y?
03 X<>Y
04 -
05 LASTX
06 X<>Y
08 X!=0?  (not equal)
09 GTO "GCD"
10 +  (add to discard the zero on the stack)
12 RTN
12 END

00 { 23-Byte Prgm }
01 LBL "LCM"
02 STO "X"
03 X<>Y
04 *  (multiply)
05 LASTX
02 RCL "X"
06 XEQ "GCD"
07 /  (divide)
08 RTN
09 END

Note that those algorithms work only for positive integers. The programs don't enforce that you have to make sure it's the case.

Test the program: 88, Enter, 56, XEQ GCD, expected result: 8
Test the program: 9, Enter, 6, XEQ LCM, expected result: 18

The algorithm

function gcd(int y, int x){
    int tmp;
    if (x>y){ // swap x and y
        tmp=x;y=x;x=tmp;
    }
    tmp=x;
    y=y-x;
    if (y==0){
	return(y);
    }
    gcd(tmp,y);
}

The LCM of x,y is: (x*y) / GCD(x,y)

Written by Guido Socher