用c++求最大公约数

C++求最大公约数可以使用辗转相减法或者辗转相除法。

1. 辗转相减法：

辗转相减法的基本思想是用两个数的差不断替换两个数中较大的那个数，直到两个数相等，这个相等的数就是它们的最大公约数。

代码如下：

int gcd(int a, int b)
{
    while(a != b)
    {
        if(a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

2. 辗转相除法：

辗转相除法的基本思想是用两个数的余数不断替换两个数中较大的那个数，直到余数为0，这个时候另一个数就是它们的最大公约数。

代码如下：

int gcd(int a, int b)
{
    int r;
    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

相关问题

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 ]

c++求最大公约数代码

以下是C++求最大公约数的代码：

#include<iostream>
using namespace std;

int gcd(int x, int y) {
    int i;
    for(i = 1000; i > 0; i--) {
        if((x % i == 0) && (y % i == 0)) {
            return i;
        }
    }
}

int main() {
    int a, b, res;
    cin >> a >> b;
    res = gcd(a, b);
    cout << res << endl;
    return 0;
}

该代码使用了暴力遍历的方法，从1000开始递减遍历，找到a和b的最大公约数后返回。