C语言_算法_输入两个正整数m和n 求其最大公约数与最小公倍数

(1)方式一：碾转相除法

#include <stdio.h>#include <math.h> /*输入两个数，求最大公约数 与最小公倍数分析关系：最小公倍数=两数的积/最小公倍数 */ int main() {int m,n,i,temp,temp1;printf("输入两个整数以,隔开\n");scanf("%d,%d",&m,&n);temp1=m*n;//两数的积 i=n;if(n>m){//判断大数做被除数 temp=m;m=n;n=temp;}while(n!=0){temp=m%n;//碾转相除法得最小公倍数m=n;n=temp;}printf("最小公倍数：%d\n",m);printf("最大公约数：%d",temp1/m);return 0;}

（2）方式二 分解质因数法

#include <stdio.h>#include <math.h> // 输入两个数的最大公因数 int main() {int m,n,s,i;scanf("%d,%d",&m,&s);printf("%d,%d 的最大公约数是：",m,s);n=(m>s)?s:m;for(i=n;i>0;i--){if((m%i!=0)||(s%i!=0))continue;printf("%2d\n",i);printf("最小公倍数%5d",m*s/i); return 0;}return 0;}

（3）更相减损术法

#include <stdio.h>#include <math.h> /*输入两个数，求最大公约数 与最小公倍数分析关系：最小公倍数=两数的积/最小公倍数 */ int main() {int CommonDivisor(int m,int n);int m,n,i,temp2;printf("输入两个整数以,隔开\n");scanf("%d,%d",&m,&n);temp2=m*n;n=CommonDivisor(m,n);printf("最小公倍数：%d\n",temp2/n);printf("最大公约数：%d",n);return 0;}int temp1=1;int CommonDivisor(int m,int n){int temp;extern int temp1;if(m%2!=0||n%2!=0){while(n!=0){if(n>m){temp=m;m=n;n=temp;}temp=m-n;m=n;n=temp;}return m*temp1;}else{m /=2;n /=2;temp1*=2;CommonDivisor(m,n);}}