Petitverse

整数AとBの最大公約数を求めるとします。
AとBのうち、小さいほうの数をMとします。
暫定の最大公約数Dを、最初は1と仮定します。

まず、Aを2で割ります。Bも2で割ります。どっちも余りが0なら、Dを2に更新します。
次に、Aを3で割ります。Bも3で割ります。どっちも余りが0なら、Dを3に更新します。
この余りチェックを、割る数がMになるまで繰り返します。

繰り返しチェックが終わったときのDが、AとBの最大公約数になります。

>ユーグリットの互除法(？)以外でお願いします。<
一気に難易度が上がった。
まぁ割り算しなければ互除法ではないので問題ない。(ネタ回答)
DEF GCD(N,M)
　IF N<M THEN SWAP N,M
　IF M==0 THEN RETURN N
　RETURN GCD(M,N-M)
END

SatoshiMcCloudさん
その手があった。


真面目(？)な回答(ユークリッドの互除法)
DEF GCD(N,M)
　IF M==0 THEN RETURN N
　RETURN GCD(M,N MOD M)
END

>行列まだ習ってないとかうせやろ！？もしかして文系？
とか言ってたから当然ユークリッドの互除法(数Aで習う)は知ってるものだと思ってました...

>ヒント
>AとBの最大公約数とBとA mod Bの最大公約数は等しい

これをプログラムで書くとこういうことです。
DEF GCD(A,B)
　RETURN GCD(B,A MOD B)
END
ただしB=0のときMOD 0はできないから、その時だけはAとBの最大公約数を計算しないといけません。
B=0の時、Aと0の最大公約数はAです。
なので
　IF B==0 THEN RETURN A
を追加すれば完成。
DEF GCD(A,B)
　IF B==0 THEN RETURN A
　RETURN GCD(B,A MOD B)
END

ところで、この関数はGCD(B,A MOD B)で呼び出してるから、
そもそもB=0ということはその前にA MOD B=0だったということですよね。
なので IF B==0 THEN の代わりに、IF A MOD B==0 THEN と先に調べておいても結果は同じです。
この時 RETURN A のAは、呼び出す前はBだったので、RETURN B になりますよ。
DEF GCD(A,B)
　IF A MOD B==0 THEN RETURN B '(A←B、B←A MOD Bに置き換え。)
　RETURN GCD(B,A MOD B)
END

このように「AとBの最大公約数とBとA mod Bの最大公約数は等しい」を繰り返し使って最大公約数を求める方法のことを「ユークリッドの互除法」(または単に「互除法」)と言います。

じゃあ互除法使わない方法でも。
SatoshiMcCloudさんのやり方において、逆に割る数をM、M-1、M-2、...と減らして調べていけば、最初に見つかったところでRETURNできて少し速いかも。
DEF GCD(A,B)
　FOR M=MIN(A,B) TO 1 STEP -1
　　IF A MOD M==0 && B MOD M==0 THEN RETURN M
　NEXT
END