Java最大公約数を求める(アルゴリズムの詳細な解釈付き)

Javaは最大公約数を求めます-アルゴリズムの証明を持ちます

キーコード

は、2つの数の最大公約数が2つの数の余剰数と小さい整数の最大公約数

に等しいことを証明する.

結論

キーコード

/**
     *   a > b
     * @param a
     * @param b
     * @return
     */
    public static int maxDivisor(int a, int b){
        int n = a;
        int m = b;
        int r = 0;
        while(m!=0){
            r = n%m;
            n = m;
            m = r;
        }
        return n;
    }

証明:2つの数の最大公約数は2つの数の余剰数と小さい整数の最大公約数に等しい
a、bの最大公約数をd(a>b)と仮定し、そのうちa%b=r(r>0)であり、b、rの最大公約数を求めるのもd証明過程であるa、bの最大公約数がdであるため、a=xd、b=ydである.a%b=rであるため、a=zb+rであるため、a=yzd+r=xdであるため、r=(x−yz)d、すなわちrはdを除去する.従ってd時b,rの約数.以下、約数の範囲を示す.
b、rに約数gがあると仮定すると、b=ng、r=mgであり、a=zng+mg=(zn+m)gであり、gもa、bの約数である.a,bの最大公約数はdであるため、g<=dであるため、b,rの最大公約数はdである
結論
コード中のm=0の場合、前のサイクルでn%m=0であることがわかり、すなわち、mはこのサイクルにおけるm、nの最大公約数であり、最初のm、nの最大公約数でもある