【C++】两个或多个数的最大公约数(gcd)、最小公倍数(lcm)算法 |
您所在的位置：网站首页 › gcd格式 › 【C++】两个或多个数的最大公约数(gcd)、最小公倍数(lcm)算法 |
|
最大公约数、最小公倍数算法
1、求最大公约数（gcd）（1）更相减损术（2）辗转相除法（欧几里得算法）（3）求多个数的最大公约数
2、求最小公倍数（lcm）（1）求两个数的最小公倍数（2）求多个数的最小公倍数
1、求最大公约数（gcd）
最大公约数（greatest common divisor，简写为 gcd ；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。 （1）更相减损术注意，更相减损术算法的耗时长，一般不推荐使用。 更相减损术百度百科 代码如下： 非递归形式 int gcd(int a, int b) { while (a != b) { if (a > b)a -= b; else b -= a; } return a; }递归形式 这个gcd函数在正int型内完全通用，返回a,b的最大公约数 但是当a,b之间差距较大时（如100000倍）会导致错误（栈过深） int gcd(int a, int b) { if (a == b)return a; else if (a > b)a -= b; else b -= a; return gcd(a, b); } （2）辗转相除法（欧几里得算法）求最大公约数，一般都会使用此算法。 欧几里得算法百度百科 代码如下： 非递归形式： int gcd(int a, int b) { int temp = b; while (a % b) { //辗转相除 temp = a % b; a = b; b = temp; } return temp; }递归形式一： int gcd(int a, int b) { if (a % b == 0) return b; else return gcd(b, a % b); }递归形式二： int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } （3）求多个数的最大公约数我们可以先求出前两个数的最大公约数(a)，再用这个最大公约数(a)与下一个数求出它们的最大公约数(b)，不断循环直到计算完所有数。 #include using namespace std; int gcd(int a, int b) { if (a % b == 0) return b; else return gcd(b, a % b); } int main() { int a[8] = { 32,16,12,24,36,20,40,28 }; //最大公约数：4 int L = sizeof(a) / sizeof(int); //L为元素个数 int m = a[0]; //初始化最大公约数：a[0] for (int i = 1; i return a > b; } int gcd(int num[], int n) //求多个数的最大公约数的算法 { sort(num, num + n, cmp); while (num[0] != num[n - 1]) { for (int i = 0; i int a[8] = { 32,16,12,24,36,20,40,28 }; //最大公约数：4 int L = sizeof(a) / sizeof(int); //L为元素个数 cout int temp = a * b; temp = temp / gcd(a, b); return temp; } （2）求多个数的最小公倍数我们可以先求出前两个数的最小公倍数(a)，再用这个最小公倍数(a)与下一个数求出它们的最小公倍数(b)，不断循环直到计算完所有数。 #include using namespace std; int gcd(int a, int b) { if (a % b == 0) return b; else return gcd(b, a % b); } int lcm(int a, int b) { int temp = a * b; temp = temp / gcd(a, b); return temp; } int main() { int a[4] = { 40,20,10,30 }; //最小公倍数：120 int L = sizeof(a) / sizeof(int); //L为元素个数 int m = a[0]; //初始化最小公倍数：a[0] for (int i = 1; i if (a % b == 0) return b; else return gcd(b, a % b); } ll lcm(ll a, ll b) { ll temp = a * b; temp = temp / gcd(a, b); return temp; } int main() { int n; while (cin >> n) { for (int i = 0; i m = m * a[i] / gcd(m, a[i]); } cout |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |