2つの数あるいは複数の数の最大公約数のアルゴリズムとその実現を求めます

2つの数あるいは複数の数の最大公約数のアルゴリズムとその実現を求めます
1、2つの数の最大公約数:
1、ユークリッドアルゴリズム
ユークリッドアルゴリズムは、2つの整数a,bの最大公約数を計算するために、転がり相除去法とも呼ばれる.その計算原理は以下の定理に依存する:定理:gcd(a,b)=gcd(b,a mod b)は、aがa=kb+rとして表すことができ、r=a mod bはdがa,bの1つの公約数であると仮定し、d|a,d|bがあり、r=a−kbであるため、d|rは(b,a mod b)の公約数であると仮定し、d|b,d|rである.しかし、a=kb+rであるため、dも(a,b)の公約数であるため(a,b)と(b,a mod b)の公約数は同じであり、その最大公約数も必然的に等しい.ユークリッドアルゴリズムはこの原理に基づいて行われていることを証明し、そのアルゴリズムはC++言語で記述されている.void swap(int & a, int & b){ 
     int c = a; 
       a = b; 
       b = c; 
} 

int gcd(int a,int b){ 
     if(0 == a ){ 
         return b; 
     } 
     if( 0 == b){ 
         return a; 
     } 
     if(a > b){ 
         swap(a,b); 
     } 
     int c; 
     for(c = a % b ; c > 0 ; c = a % b){ 
           a = b; 
           b = c; 
     } 
     return b; 
}
2、Steinアルゴリズムユークリッドアルゴリズムは2つの数の最大公約数を計算する伝統的なアルゴリズムであり、理論的にも効率的にも優れている.しかし、致命的な欠陥があり、この欠陥は大きな素数の時にしか現れない.現在のハードウェアプラットフォームを考慮すると、一般的に整数は最大64ビットであり、このような整数に対して、2つの数の間のモジュールを計算するのは簡単である.ワード長が32ビットのプラットフォームでは、32ビットを超えない2つの整数を計算するモードは、1つの命令周期しか必要ありませんが、64ビット以下の整数モードを計算するのは、いくつかの周期にすぎません.しかし、より大きな素数に対しては、このような計算プロセスはユーザーによって設計されなければならず、64ビットを超える2つの整数のモジュールを計算するために、ユーザーは複数の数除算手算プロセスに類似した試商法を採用しなければならないかもしれない.このプロセスは複雑であるだけでなく、多くのCPU時間を消費している.現代の暗号アルゴリズムでは,128ビット以上の素数の計算が要求される場合が多く,このようなプログラムの設計は除算と型取りを捨てることを切に望んでいる.SteinアルゴリズムはJ.Stein 1961年に提案され,この方法も2つの数を計算する最大公約数である.ユークリッドアルゴリズムとは異なり,Steinアルゴリズムは整数のシフトと加減法のみであり,これはプログラム設計者にとって福音である.Steinアルゴリズムの正確性を説明するためには、まず、gcd(a,a)=a、すなわち、1つの数とそれ自身の公約数が、その自身のgcd(ka,kb)=k gcd(a,b)、すなわち最大公約数演算と倍乗演算とを交換可能であり、特に、k=2の場合、2つの偶数の最大公約数が必ず2でC++/javaを除去してを実現できることを説明します// c++/java stein  
int gcd(int a,int b){ 
     if(a<b){//arrange so that a>b 
         int temp = a; 
           a = b; 
           b=temp; 
     } 
     if(0==b)//the base case 
        return a; 
     if(a%2==0 && b%2 ==0)//a and b are even 
         return 2*gcd(a/2,b/2); 
     if ( a%2 == 0)// only a is even 
         return gcd(a/2,b); 
     if ( b%2==0 )// only b is even 
         return gcd(a,b/2); 
     return gcd((a+b)/2,(a-b)/2);// a and b are odd 
}
二、複数の数の最大公約数:(python実現:配列aの中で最小の、2から最小のサイクルを取り出し、その中で最大の配列の中のすべての数で除去できるその数を探し出し、最大公約数である)
def gcd(a):
    a.sort()
    min = a[0]
    result = 1
    for i in range(2, min+1):
        flag = True
        for j in a:
            if j % i != 0:
                flag = False
        if flag == True:
            result = i
    return result
ユークリッドアルゴリズムは1行で済むと言われています.
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}