方法１

最大公約数は小さい方の数を越えることがないので、小さい数から始めて、１つずつ減らしていった数で２つの数を割る。それぞれ割ったときの余りが両方とも０になるまで繰り返して見つけるプログラム

方法２

大きい方の数を小さい方の数で割って余りを求め、この余りで小さい方の数を余りで割る。このことを余りが０になるまで繰り返して見つける（ユークリッド互除法）プログラム