最大公约数(General common divisor)
方法一：遍历查找法
从a,b中小的哪个数开始，a, a-1, a-2…逐一查找，找到第一个满足同时被a,b整除的条件就终止。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /**************************************************************** * Description: GCD loop * Author: Alex Li * Date: 2024-03-26 12:45:13 * LastEditTime: 2024-03-26 12:50:16 ****************************************************************/ #include <iostream> #include <cmath> using namespace std; int main(){ int a,b; cin>>a>>b; for(int i=min(a,b);i>1;i--){ if(a%i==0&&b%i==0){ cout<<i; break; } } 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 | /**************************************************************** * C++ 用辗转向减法求最大公约数 * date： 2022-5-2 * verstion: 1.0 * author: Alex Li ****************************************************************/ #include<iostream> using namespace std; int gcd(int a,int b){ if(b==a)return a; if(a<b) swap(a,b); return gcd(b,a-b); } int main(){ int a,b; cout<<"input two number: "; cin>>a>>b; cout<<gcd(a,b); return 0; } |
方法三：欧几里德算法又叫辗转相除法。
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。
例一：求26 和12两个整数的最大公约数
26/12=2(余2)
12/2=6(余0)
所以2为两数的最大公约数。
例二：求3139和2117的最大公约数
3139/2117=1(余1022)
2117/1022=2(余73)
1022/73=0
所以73为两数的最大公约数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /**************************************************************** * C++ 用欧几里德算法求最大公约数 * date： 2023-3-11 * verstion: 1.2 * author: Alex Li ****************************************************************/ #include<iostream> using namespace std; int gcd(int a,int b){ if(a%b==0)return b; return gcd(b,a%b); } int main(){ int a,b; cout<<"input two number: "; cin>>a>>b; cout<<gcd(a,b); return 0; } |