ユークリッドの互除法

ユークリッドの互除法（Euclidean algorithm）は、最大公約数を求めるためのアルゴリズムです。

割り切れるまで割り算を繰り返します。例えば、234と177の最大公約数を求めるには、

234 ÷ 177 = 1 余り 57
177 ÷ 57 = 3 余り 6
57 ÷ 6 = 9 余り 3
6 ÷ 3 = 2 余り 0

だから、最大公約数は3となります。
コードは、再帰を使って書くと簡単です。Cで書くと、

#include 
int GCD_core(int a, int b) {

    int d = a % b;

    if(d == 0)

        return b;

    else

        return GCD_core(b, d);

}
int GCD(int a, int b) {

    /* Pythonの仕様に合わせてある */

    if(a == 0)

        return b;

    else if(b == 0)

        return a;

    else {

        int plus = b > 0;

        a = abs(a);

        b = abs(b);

        if(plus)

            return GCD_core(a, b);

        else

            return -GCD_core(a, b);

    }

}
int main(int argc, char **argv) {

    if(argc != 3) {

        puts("euclid a b.");

    }

    else {

        int a, b;

        sscanf(argv[1], "%d", &a);

        sscanf(argv[2], "%d", &b);

        printf("%d\n", GCD(a, b));

    }

}

最大公約数を求めるために、素因数分解をしてはいけません。上の例では、

234 = 2•3²•13
177 = 3•59

だから最大公約数は3となりますが、素因数分解はとても遅く、ユークリッドの互除法のほうが圧倒的に速いのです。