用辗转相除法求两个整数的最大公约数

用辗转相除法，求两个整数的最大公约数，提示需先判断两个数的大小


#include <iostream>
using namespace std;

int main()
{
    int a, b;

    cout << "Enter two integers: ";
    cin >> a >> b;

    // 首先判断a和b的大小，确保a是较大的数
    if (a < b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    // 使用辗转相除法求最大公约数
    int r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }

    // 输出结果
    cout << "The greatest common divisor of " << a << " and " << b << " is " << b << endl;

    return 0;
}

这篇除了辗转相除法，还介绍了别的，参考下：

【C语言】求最大公约数和最小公倍数_c语言求最大公约数和最小公倍数_思绪万茜的博客-CSDN博客方法一：利用定义法求最大公因数和最小公倍数#include<stdio.h>int main(){int a,b,i,j;int max=0;scanf("%d%d",&a,&b);for(i=a;;i++)//求最小公倍数{if(i%a==0&&i%b==0)//用大于等于a和b的数i(i大于等于a和b，无上限)分别除以a和b，同时除尽的第一个数即为最小公倍数break;//然后循环结束}for(j=1;j&

https://blog.csdn.net/m0_66304425/article/details/123920248


#include <iostream>
using namespace std;

int main()
{
    int a, b, t;
    cout << "Enter two positive integers: ";
    cin >> a >> b;

    // Swap a and b if necessary so that a <= b
    if (a > b) {
        t = a;
        a = b;
        b = t;
    }

    // Use the Euclidean algorithm to find the GCD of a and b
    while (a != 0) {
        t = a;
        a = b % a;
        b = t;
    }

    cout << "The GCD is " << b << endl;
    return 0;
}

首先从标准输入中读取两个正整数a和b，然后在使用辗转相除法之前检查a和b的大小。如果a比b大，则交换它们的值。

接下来，程序使用辗转相除法找到a和b的最大公约数。在每次循环中，该算法计算b除以a的余数，并将其赋值给b，将原来的b赋值给a，直到a为0。此时，变量b中存储的值就是a和b的最大公约数。

最后，程序输出最大公约数b的值并返回0作为结束代码。

帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7572784
这篇博客你也可以参考下：利用辗转相除法求两个数的最大公约数
除此之外, 这篇博客: 习题4-7 最大公约数和最小公倍数求两个给定正整数的最大公约数和最小公倍数中的 代码： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

#include <stdio.h>
#include <math.h>
int main(){
 int M,N,a,b;
 int m,n,max,min,sum;
 scanf("%d %d",&M,&N);
 if(M<N){
  a=N;
  b=M;
 }else{
  a=M;
  b=N;
 }
 
 if(M<=1000&&N<=1000){
  for(int i=a; ;i--){
   if(a%i==0&&b%i==0){
    max=i;
    break;
   }
  }
  for(int k=1; ;k++){
   if((a*k)%b==0){
    min=k;
    sum=a*k;
    break;
   }
  }
 }
 printf("%d %d",max,sum);
 
 return 0;
}

您还可以看一下徐朋老师的软考高项信息系统项目管理师考试复习备考公开课课程中的软考考试介绍小节, 巩固相关知识点
以下回答由chatgpt基于相关博客总结生成:
辗转相除法是指用较大的数除较小的数，然后用余数去除较小的数，接着用上一个除数去除上一个余数，如此循环，直至余数为0，此时上一个除数为原来两个数的最大公约数。因此，不需要在实施辗转相除法之前先判断两个整数的大小。以下是使用辗转相除法求解最大公约数的代码：
```
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
```
其中，a和b分别为输入的两个整数。由于Python的语法比较简洁，直接使用while循环即可实现。若a和b的值较大时，该算法会比较高效。
关于如何求两个整数的最小公倍数，请参考以下代码：
```
def lcm(a, b):
    return a * b // gcd(a, b)
```
其中，a和b分别为输入的两个整数。最小公倍数等于两个整数的乘积除以它们的最大公约数。由于Python的整除运算符"//"可以直接进行整数除法并向下取整，因此可以直接使用该符号来计算最小公倍数。