C语言求两个正整数的最小公倍数 c语言

这里将介绍求两个正整数的最小公倍数（Least Common Multiple，LCM）的方法。提供两种主要思路，一种是直接根据最小公倍数的定义设计算法，一种是由最大公约数计算得出。下面来介绍这两种方法。
定义法求解两个正整数的最小公倍数的第一种思路，根据定义设计算法，最小公倍数的本质是一个最小的能同时被两整数整除的自然数。我们先比较两数大小，从较大数开始向上递增，直到找到那个最小公倍数。
代码如下：

#include int main() { int i=0; int m,n,temp; printf("请输入两个正整数:"); scanf("%d %d",&m,&n); if(m0; i++)//从较大数开始寻找符合条件的最小公倍数 { if(i%m==0 && i%n==0) { printf("%d和%d的最小公倍数是%d",m,n,i); break; } } return 0; }

辅助法求最小公倍数也可以借助最大公约数辅助计算，公式为最小公倍数=两数的乘积/最大公约（因）数。解题时避免将两个问题混淆。
连续整除检测法这种方法的实现原理是，先取出两个数中的较小数，赋值给temp(temporary)，接着用其中一个数与temp求余，若余数不为0，则temp-1，循环该步骤直到余数为0。再用另一个数，重复此步骤，最后得出的值利用公式计算得到这两个数的最小公倍数。
代码如下：

#include int main() { int i=0; int m,n,temp; printf("请输入两个正整数:"); scanf("%d %d",&m,&n); if(m>n) { temp=n; }else//m=n在此不需要单独讨论 { temp=m; } for(i=temp; i>0; i--)//如果从i=1开始，得出公约数也无法保证其为最大公约数。 { if(m%i==0 && n%i==0) break; } printf("%d和%d的最小公倍数是%d",m,n,m*n/i); return 0; }

欧几里得算法这种方法的实现原理是求两个正整数的余数r（remainder），再用两个正整数中的较小数与其再求余直到余数为0时，此时的较小数就是最大公约数。最后利用公式计算得到这两个数的最小公倍数。
【C语言求两个正整数的最小公倍数】代码如下：

#include int main() { int m,n,r; printf("请输入两个正整数:"); scanf("%d %d",&m,&n); int x=m*n; //x用于存放m与n的乘积 printf("%d%和%d的最小公倍数是",m,n); //此时输出m和n的值还没改变 r=m%n; while(r!=0)//不用比较大小，若m小于n，则会在第一遍循环交换位置 { m=n; n=r; r=m%n; } printf("%d",x/n); return 0; }

相减法这种方法比较易于理解，原理是先判断两个正整数大小，并将较大数与较小数的差值赋给较大数，循环此步骤直到两数相等，此时得出最大公约数。最后利用公式计算得到这两个数的最小公倍数。
代码如下：

#include int main() { int m,n; printf("请输入两个正整数:"); scanf("%d %d",&m,&n); int x=m*n; //x用于存放m与n的乘积 printf("%d%和%d的最小公倍数是",m,n); while(m!=n); { if(m>n) { m=m-n; }else { n=n-m; } } printf("%d",x/n); return 0; }

最后把这几种方法构建为函数lcm并尝试调用。
代码如下：

#includeint lcm1(int m,int n) { int i=0; int temp; if(m0; i++)//从大数开始寻找符合条件最小公倍数 { if(i%m==0 && i%n==0) { break; } } return i; }int lcm2(int m,int n) { int i=0; int temp; if(m>n) { temp=n; }else//m=n在此不需要单独讨论 { temp=m; } for(i=temp; i>0; i--)//如果从i=1开始，得出公约数也无法保证其为最大公约数。 { if(m%i==0 && n%i==0) break; } return i; }int lcm3(int m,int n) { int r=m%n; while(r!=0)//不用比较大小，若m小于n，则会在第一遍循环交换位置 { m=n; n=r; r=m%n; } return n; }int lcm4(int m,int n) { while(m!=n) { if(m>n) { m=m-n; }else { n=n-m; } } return n; }int main() { printf("请输入两个正整数: "); int x,y; scanf("%d %d",&x,&y); int a=lcm1(x,y); int b=lcm2(x,y); int c=lcm3(x,y); int d=lcm4(x,y); printf("%d和%d的最小公倍数为%d\n",x,y,a); printf("%d和%d的最小公倍数为%d\n",x,y,x*y/b); printf("%d和%d的最小公倍数为%d\n",x,y,x*y/c); printf("%d和%d的最小公倍数为%d",x,y,x*y/d); return 0; }

尝试运行结果：