C++编程 求最大公约数和最小公倍数

C++编程 求最大公约数和最小公倍数 1.最大公约数 解题思想:
?1.辗转相除法(欧几里德算法),定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
2.辗转相减法(尼考曼彻斯法),其特色是做一系列减法,从而求得最大公约数。3.穷举法 从上往下减,保证最大!
代码实现:

#include using namespace std; //辗转相除法(欧几里德算法) int measure1(int x, int y) { int z = y; while(x%y!=0) {//定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 z = x%y; x = y; y = z; } return z; }//辗转相减法(尼考曼彻斯法) int measure2(int a,int b) { while(a != b) {//其特色是做一系列减法,从而求得最大公约数 if(a>b) { a = a - b; } else { b = b - a; } } return a; }//穷举法从上往下减,保证最大! int measure3(int x,int y) { int temp = 0; for(temp = x ; ; temp-- ) { if(x%temp == 0 && y%temp==0) break; } return temp; }void main(){ int x,y; cout<<"请输入两个数字,并在中间用空格隔开:"; cin>>x; cin>>y; cout<<"辗转相除法得到的最大公约数为:"<

效果图展示:
C++编程 求最大公约数和最小公倍数
文章图片

2.最小公倍数 解题思想:
?1.穷举法,从两者中最大的数开始,向上加,直到可以使对两数同时取余都为零。2.两个整数的最小公倍数等于两整数之积除以最大公约数。
代码实现:
#include using namespace std; void main(){ int n1, n2, max; cout << "输入两个数: "; cin >> n1 >> n2; // 获取最大的数 max = (n1 > n2) ? n1 : n2; do { if (max % n1 == 0 && max % n2 == 0) { cout << "LCM = " << max<

【C++编程 求最大公约数和最小公倍数】效果图展示:
C++编程 求最大公约数和最小公倍数
文章图片

    推荐阅读