要求：
求两个不全为0的非负整数m和n的最大公约数，记为gcd(m,n).要求：分别使用欧几里德算法、连续整数检测算法、公因数算法等实现
一、欧几里德算法（辗转相除）
//欧几里德算法const unsigned int Gcd1(unsigned int a, unsigned int b)//a>b{ if (a%b != 0) { if (a > b) Gcd1(b, a%b); } else if (a%b == 0) return b;
}
二、连续整数检测算法
//连续整数检测算法const unsigned int Gcd2(unsigned int a, unsigned int b)//a>b{ //最多进行√n次即可，本次利用n/2。 int number = b / 2; for (int n = number + 1; n >0; n--) { if (a%b == 0) return a; if (a%n == 0&&b%n==0) { return n; } }
}
三、因数法
//分解质因数法
//判断是否是质数 bool IsPrimeNumber(int n) { if (n == 2) return true; if (n % 2 == 0) return false; int sqrtn = (int)sqrt((double)n); bool flag = true; for (int i = 3; i <= sqrtn; i += 2) { if (n%i == 0) flag = false; } return flag; } bool Resolve(unsigned int Number, int num[])//分解函数 { int number = Number; int n = 0, j = 1;//循环次数---->因数的个数 int sqrtn = (int)sqrt((double)Number);//num表示因数个数 for (n; n <= sqrtn; n++) { if (IsPrimeNumber(number)) { num[j] = number; num[0]++; j++; return true; } for (int i = 2; i <=sqrtn; i++) { if (number%i == 0) { num[j] = i; number = number / i; num[0]++; j++; } break; } } } const unsigned int Gcd3(unsigned int a, unsigned int b) { Resolve(a, Numm); Resolve(b, Numn); int i = 1; unsigned int product = 1; for (i=1; i <= Numm[0]; i++) { for(int j=1;j<= Numn[0];j++) if (Numm[i] == Numn[j]) { product *= Numm[i]; Numn[j] = 1; break; } } return product;}
完整代码
ps：三种在一个main中实现，另外两个用来存放因数的数字，可以利用动态数组存放。本算法利用上限32作为数组宽度
#include<iostream>#include<cmath>using namespace std;int Numm[32] = { 0 };int Numn[32] = { 0 };void Sort(unsigned int &a, unsigned int &b){ unsigned int number=0; if (a < b) { number = a; a = b; b = number; }}//欧几里德算法const unsigned int Gcd1(unsigned int a, unsigned int b)//a>b{ if (a%b != 0) { if (a > b) Gcd1(b, a%b); } else if (a%b == 0) return b;}//连续整数检测算法const unsigned int Gcd2(unsigned int a, unsigned int b)//a>b{ //最多进行√n次即可，本次利用n/2。 int number = b / 2; for (int n = number + 1; n >0; n--) { if (a%b == 0) return a; if (a%n == 0&&b%n==0) { return n; } }}//分解质因数法//判断是否是质数bool IsPrimeNumber(int n){ if (n == 2) return true; if (n % 2 == 0) return false; int sqrtn = (int)sqrt((double)n); bool flag = true; for (int i = 3; i <= sqrtn; i += 2) { if (n%i == 0) flag = false; } return flag;}bool Resolve(unsigned int Number, int num[]){ int number = Number; int n = 0, j = 1;//循环次数---->因数的个数 int sqrtn = (int)sqrt((double)Number);//num表示因数个数 for (n; n <= sqrtn; n++) { if (IsPrimeNumber(number)) { num[j] = number; num[0]++; j++; return true; } for (int i = 2; i <=sqrtn; i++) { if (number%i == 0) { num[j] = i; number = number / i; num[0]++; j++; } break; } }}const unsigned int Gcd3(unsigned int a, unsigned int b){ Resolve(a, Numm); Resolve(b, Numn); int i = 1; unsigned int product = 1; for (i=1; i <= Numm[0]; i++) { for(int j=1;j<= Numn[0];j++) if (Numm[i] == Numn[j]) { product *= Numm[i]; Numn[j] = 1; break; } } return product;}int main(){ unsigned int m, n; cout << "输入两个数据:"; cin >> m >> n; Sort(m, n); if (m == n) cout << "最大公约数为:" << m << endl; cout<<Gcd1(m, n)<<endl; cout << Gcd2(m, n) << endl; cout << Gcd3(m, n) << endl; return 0;}
