最大公約数~ユークリッドの互除法~

By tonNo Comments

今回は最大公約数を求めるアルゴリズム
ユークリッドの互除法とは、古代ギリシアの数学者ユークリッドさんが書いた『原論』の中に出てくるもので明示的に記述された最古のアルゴリズムらしいです
ちなみに、ユークリッドは英語名で本当はエウクレイデスだそうな
※エウクレイデス(Ευκλείδης (Eukleides),ラテン語名:Euclides,英語名:Euclid(ユークリッド)

さて、本題ですが、またwikipediaさんを引用w
2 つの自然数(または整式) a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

うーん・・・なにを言っているのやら・・・w
さっぱりなので、もっと分かりやすく解説してみます(自分もいろんなとこを参考にしながらだからあってるかわからないけど・・・w)

a と b との最大公約数は b と r との最大公約数に等しいという性質 について
30と18をつかって考えてみます
30÷18=1あまり12 です これは
30=1×18+12 と書くことができます
この性質は30と18の最大公約数は18と12の最大公約数と同じと言っています
これは
30=1×18+12 から 18と12を割り切る数は30でも割り切れ、また
12=30-1×18 から 30と18を割り切る数は12でも割り切れるからです
割り切れる数をどれだけ足しても割り切れるってことですね

これをどんどん繰り返していきます
30と18の最大公約数
| |    30÷18=1あまり12
18と12の最大公約数
| |    18÷12=1あまり6
12と6の最大公約数
| |    12÷6=2あまり0
あまりが0になったときの除数、つまり6が最大公約数ということになります

わかりやすくなってないって・・・・・?w

これをアルゴリズムの手順として整理すると
1.二つの整数をa、bとする
2.b=0ならaを最大公約数として終了
3.a÷bのあまりをb、元のbをaとして2.にもどる

Javaで書くとこんな感じ

EuclidGCD.java


public class EuclidGCD{
    static int gcd(int a, int b){
    // b=0ならaを最大公約数として終了
        if(b == 0){
            return a;
        }else{
       // a÷bのあまりをb、元のbをaとして2.にもどる
            return gcd(b, a % b);
        }
    }

    public static void main(String[] args){    //aとbの最大公約数を求めます
        int a = 30;
        int b = 18;

        System.out.println(gcd(a,b));
    }
}

短い!w

ユークリッドの互除法は計算回数もかなり少なくてすむみたいで、
割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の 5 倍繰り返せば、最大公約数に達する。(ラメの定理)
らしいです。1000桁の数なら5000回計算すれば求まるってことか はやw
素直に素因数分解してたらどれだけ時間がかかることやら・・・w


アルゴリズム

Leave your Comment

メールアドレスが公開されることはありません。

Blue Taste Theme created by Jabox