最大的公約數算法其他比歐幾里德的

Question

我應該基本上生成3個不同的算法來找到GCD（a，b）。

其中之一是歐幾里得的版本，所以我需要兩個。

實現在C＃中完成。

對此提出建議？

Answer 1

（請注意，計算gcd(a,b)的時候，我們可以假設，a <= b;如果這是不正確的，我們可以只交換它們）

歐幾里德算法肯定是計算GCD的最有效方式。但是，如果你需要另外兩個（低效率）的方式來計算gcd(a,b)，也有很多：

1. 從a啓動和下去的時候，測試每個數，看是否都劃分和ab。

2. 黃金比化a和b（獲得質數的多集），並返回這些多集的交集的產品。

3. 查找a的所有因數，並測試它們是否從a開始分隔b並且正在關閉。

4. 查找lcm(a,b)通過測試，其中b, 2*b, 3*b, ...是整除a，並返回a*b/(lcm(a,b))。

1和4可能最容易實現，因爲它們不涉及因式分解。

重要的是要注意一些邊緣情況：所有x > 0的gcd(0,x) = x，而gcd(0,0)未定義。技術上，我想gcd(a,b) = gcd(abs(a), abs(b))涵蓋的情況下輸入可能是負面的。

Answer 2

這是三個最常用的算法：

public static uint FindGCDModulus(uint value1, uint value2) 
{ 
while(value1 != 0 && value2 != 0) 
{ 
     if (value1 > value2) 
     { 
       value1 %= value2; 
     } 
     else 
     { 
       value2 %= value1; 
     } 
} 
return Math.Max(value1, value2); 
    } 

public static uint FindGCDEuclid(uint value1, uint value2) 
    { 
while(value1 != 0 && value2 != 0) 
{ 
     if (value1 > value2) 
     { 
       value1 -= value2; 
     } 
     else 
     { 
       value2 -= value1; 
     } 
} 
return Math.Max(value1, value2); 
} 

public static uint FindGCDStein(uint value1, uint value2) 
{ 
if (value1 == 0) return value2; 
if (value2 == 0) return value1; 
if (value1 == value2) return value1; 

bool value1IsEven = (value1 & 1u) == 0; 
bool value2IsEven = (value2 & 1u) == 0; 

if (value1IsEven && value2IsEven) 
{ 
     return FindGCDStein(value1 >> 1, value2 >> 1) << 1; 
} 
else if (value1IsEven && !value2IsEven) 
{ 
     return FindGCDStein(value1 >> 1, value2); 
} 
else if (value2IsEven) 
{ 
     return FindGCDStein(value1, value2 >> 1); 
} 
else if (value1 > value2) 
{ 
     return FindGCDStein((value1 - value2) >> 1, value2); 
} 
else 
{ 
     return FindGCDStein(value1, (value2 - value1) >> 1); 
} 
} 

Answer 3

這是選擇之一：

public static int gcd(int x, int y) { 
    int result = 0; 

    if (x<0) { 
     x = -x; 
    } 
    if (y<0) { 
     y = -y; 
    } 
    if (x == 0){ 
     result = y; 
    } 
    if (y == 0){ 
     result = x; 
    } 
    for (int i = 1; i < x+1; i++) { 

     if (x % i == 0) { 

      if (y % i == 0) { 
       result = i; 
      } 
     } 
    } 
    return result; }