C++ 求最大公约数

根据提供的引用内容来看，有三种方法可以求解最大公约数。

方法一，通过辗转相除法来求解最大公约数。这种方法的实现代码如下：

#include<iostream>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    int a=1; //默认在最大公约数为1
    int times = 0;
    if(n%m==0||m%n==0) //若nm直接能整除，则最大公约数即是较小那个的数
    { 
        times++;
        m = m < n ? m : n;
    }
    while((a=n%m)!=0) 
    { 
        times++;
        n=m; 
        m=a; 
    } 
    cout<<"循环次数为："<<times<<endl; 
    cout<<"最大公约数为："<<m<<endl; 
    return 0; 
}

方法二，通过从较小数开始依次找到能同时被两个数整除的第一个整数来求解最大公约数。这种方法的实现代码如下：

#include<iostream>
using namespace std;
int main() {
    int n,m;
    int times = 0;
    cin>>n>>m; //输入两个数 
    int x = n<m?n:m; //m,n的最大的公约数永远不可能是较大的那个数，只可能是较小的数
    for(x;x>=1;x--) { 
        times++;
        if(n%x==0&&m%x==0) //x正好被n,m整除，则找到了x
            break; 
    } 
    cout<<"循环次数为："<<times<<endl; 
    cout<<"最大公约数为："<<x<<endl; 
    return 0; 
}

方法三，通过差和减数相等的方式求解最大公约数，公式为：最大公约数=相等的数*(2^除以二的次数）。这种方法的实现代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a, b, num=0,t;
    cin >> a >> b;
    if (a == b){
        cout << a << endl;
        return 0;
    }
    t=a,a = max(a, b), b = min(t, b);
    while ((a % 2 == 0) && (b % 2 == 0)){
        a /= 2, b /= 2, num++;
    }
    while (b != a - b){
        t=a-b,a = max(b, t), b = min(b, t);
    }
    cout << b * (1<<num) << endl;
    return 0;
}

以上是求解最大公约数的三种方法和对应的实现代码。通过选择其中一种方法，根据输入的两个数的不同情况，可以得到最大公约数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* [【C++】求两个数的最大公约数——方法大全](https://blog.csdn.net/ly_6699/article/details/90719315)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *3* [C++之 最大公约数求法](https://blog.csdn.net/lxiisbshcuia/article/details/124401871)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]