How to get the greatest common divisor.


Find the GREATEST common divisor for two non-zero positive numbers M and N.

IF m < n THEN SWAP m, n
DO
r = m MOD n
IF r = 0 THEN EXIT DO
m = n
n = r
LOOP

PRINT "Greatest common divisor = "; n


Again, excruciatingly simple. Just keep modding:

m | n
100 | 80
80 | 100 MOD 80 = 20
20 | 80 MOD 20
20 | 0

20, or (80 MOD (100 MOD 80)), is the GCD.


GreatestCommonDivisor - page last edited 2006-10-31 22:20:03 by 24.128.143.175 (home) (edit)
Blast WIKI - by RoboticBoy - edited and tweaked for our evil purposes by Hexadecimal Disaster