最大公约数(Greatest Common Divisor)

穷举法

break语句
您可以在任何循环中使用break语句。
它导致程序执行到切换或循环后的下一条语句。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int  main(){
    int a,b,gcd;
    cout<<"input number: ";
    cin>>a>>b;
    gcd=min(a,b);
    while(gcd>1){
        if(a%gcd==0 && b%gcd==0){  
            break;   
        }
        gcd--;
        }
    cout<<gcd<<endl;
        return 0;
    
}

欧几里得算法（Euclidean Algorithm）

这段代码实现的是经典的，也称为辗转相除法，用于计算两个正整数的最大公约数（Greatest Common Divisor, GCD）。

你缺失的这一行代码应该是 b = r;。

完整代码实现

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main() {
    int a, b, r;    
    cin >> a >> b;// 输入两个整数   
    while (b != 0) {
        r = a % b;  // 取余数
        a = b;      // 将原来的除数作为新的被除数
        b = r;      // 将余数作为新的除数
    }

    // 当除数 b 变为 0 时，此时的被除数 a 即为最大公约数
    cout << a << endl;

    return 0;
}

逻辑解析

辗转相除法的步骤如下：

  1. 用 a 除以 b，得到余数 r。
  2. 把原来的 b 赋给 a，把刚才得到的余数 r 赋给 b。
  3. 重复上述过程，直到 b 等于 0 为止。
  4. 最后的 a 就是这两个数的最大公约数。

举个例子（计算 18 和 12）：

  • 第一轮： a=18, b=12。18/12 = 1 余6。此时 r = 6。执行后 a = 12, b = 6。
  • 第二轮： a=12, b=6。12 /6 = 2 余 0。此时 r = 0。执行后 a = 6, b = 0。
  • 循环结束： 此时 b 为 0，输出 a 的值 6。
Previous Topic
Back to Lesson
Next Topic