🌵🌵🌵前言

✨你好啊，我是“ 怪& ”，是一名在校大学生哦。
🌍主页链接：怪&的个人博客主页
☀️博文主更方向为：课程学习知识、作业题解、期末备考。随着专业的深入会越来越广哦…一起期待。
❤️一个“不想让我曾没有做好的也成为你的遗憾”的博主。
💪很高兴与你相遇，一起加油！

题目

输入两个整数 a 和 b，请你编写一个函数，int gcd(int a, int b), 计算并输出 a 和 b 的最大公约数。

• 输入格式
  共一行，包含两个整数 a 和 b。

• 输出格式
  共一行，包含一个整数，表示 a 和 b 的最大公约数。

• 数据范围
  1≤a,b≤1000

• 输入样例：
  12 16

• 输出样例：
  4

解析

解法1：递归

思路

代码

#include 

using namespace std;

int gcd(int a, int b){
    if(a%b==0) return b;
    else gcd(b,a%b);  
    
}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法2：

1、暴力从1开始除以，能整除以即得到最大公因数

#include 

using namespace std;

int gcd(int a, int b){
 
    int c=min(a,b);
    int d;
    for(int i=1;i<=c;i++){
        if(a%i==0 && b%i==0){
            d=i;  
        }
    }
    return d;
}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2、从两者最小值开始除以，能整除即得到最大公因数

#include 

using namespace std;

int gcd(int a, int b){
 
    int c=min(a,b);
    int d;
    for(int i=c;i>=0;i--){
        if(a%i==0 && b%i==0){
            d=i;  
            break;
        }
    }
    return d;
}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

❤️❤️❤️忙碌的敲代码也不要忘了浪漫鸭！