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

Blast WIKI - by RoboticBoy - edited and tweaked for our evil purposes by Hexadecimal Disaster