求解最大公约数(两种)

简介: 求解最大公约数(两种)

题目

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


输入格式

共一行,包含两个整数 a 和 b。


输出格式

共一行,包含一个整数,表示 a 和 b 的最大公约数。


数据范围

1≤a,b≤1000


输入样例:

12 16


输出样例:

4


解析

解法1:递归

思路



代码

#include <iostream>usingnamespacestd;
intgcd(inta, intb){
if(a%b==0) returnb;
elsegcd(b,a%b);  
}
intmain(){
inta,b;
cin>>a>>b;
cout<<gcd(a,b);
return0;
}



解法2:

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

#include <iostream>usingnamespacestd;
intgcd(inta, intb){
intc=min(a,b);
intd;
for(inti=1;i<=c;i++){
if(a%i==0&&b%i==0){
d=i;  
        }
    }
returnd;
}
intmain(){
inta,b;
cin>>a>>b;
cout<<gcd(a,b);
return0;
}



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

#include <iostream>usingnamespacestd;
intgcd(inta, intb){
intc=min(a,b);
intd;
for(inti=c;i>=0;i--){
if(a%i==0&&b%i==0){
d=i;  
break;
        }
    }
returnd;
}
intmain(){
inta,b;
cin>>a>>b;
cout<<gcd(a,b);
return0;
}




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


目录
相关文章
|
3月前
|
算法
求最大公约数和最小公倍数的算法
求最大公约数和最小公倍数的算法
38 0
|
存储
求解素数的筛选法
求解素数的筛选法
|
3月前
|
算法 Python
最大公约数算法
最大公约数算法
|
3月前
|
算法 Python
最小公倍数算法
最小公倍数算法
|
10月前
|
算法 C++
基本算法-欧几里德算法(辗转相除法)
基本算法-欧几里德算法(辗转相除法)
111 0
数学问题之(矩阵加速递推快速幂)
数学问题之(矩阵加速递推快速幂)
|
算法
求最大公约数和最小公倍数的几种算法
求最大公约数和最小公倍数的几种算法
107 0
求解最大公约数和最小公倍数
求解最大公约数和最小公倍数
求解最大公约数和最小公倍数
欧几里得算法,既辗转相除法。用于计算正整数a,b的最大公约数
欧几里得算法,既辗转相除法。用于计算正整数a,b的最大公约数
96 0
|
算法 BI C++
【c++】三种算法求最小公倍数与最大公约数
【c++】三种算法求最小公倍数与最大公约数
966 0