最小公倍数算法c语言
㈠ c语言穷举法求最小公倍数
"对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。"这句话分开讲会清楚一点：若干个a之和能被b所整除，或者，若干个b之和能被a所整除，那么该和数即为所求的最小公倍数。但是这个说法有个错误，这个和可能有很多，只能叫公倍数，只有最小的才是最小公倍数。
的意思举个例子：a=10，b=15。a*3
=
30，能被b=15整除，所以30是公倍数，60也行，但30是最小的，所以30是最小公倍数。如果从15看，两个15，b*2
=
30，能整除10.。。。
这段程序的过程就是模拟这个算法，先找到两个数中较大的数p，然后判断p是否能整除q，p*2是否能整除q，p*3是否能整除q。。。。。。直到找到能整除q的，就是最小公倍数了。为什么是最小呢，因为p是从小到大开始找的，第一个找到的肯定是最小公倍数。
㈡ 如何用C语言求最小公倍数。。。
我代码复制给你看。
#include<stdio.h>
int GCD(int a,int b) //GCD表示最大公约数
{
int z= a<b?a:b; //我从输入的两个数中较小的那个开始判断是不是最大公约数，不是就一直-1
while(z>=1) // 直到找到能同时被X,Y整除的数，它就是最大公约数了。
{
if(a%z==0&&b%z==0) break;//最快满足这个条件的Z就是最大公约数
z--;
}
return z;
}
int LCM(int a,int b) //LCM表示最小公倍数
{
int z=a>b?a:b; //我从输入的两个数中最大的那个开始判断是不是最小公倍数，不是就一直+1
while(z<=(a*b)) //两个非零数a,b，我们知道a*b肯定是它的公倍数 ，所以从两个数的最大那个数开始
{ //一直到a*b肯定存在最小公倍数
if(z%a==0&&z%b==0)break; //最快满足这个条件的Z就是最小公倍数
z++;
}
return z;
}
int main()
{
while(1)
{
int x,y,z,d;
printf("请输入两个整数：");
scanf("%d %d",&x,&y);
z=GCD(x,y);
d=LCM(x,y);
printf("这两个数的最大公约数是%d\n",z);
printf("这两个数的最小公倍数是%d\n",d);
printf("\n");
}
}
㈢ 用C语言编写程序求两个数的最小公倍数,并输出
如图使用辗转相除法求最小公倍数：
(3)最小公倍数算法c语言扩展阅读：
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。
它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
两个数的最大公约数是指能同时整除它们的最大正整数。
设两数为a、b（a2b），求a和b最大公约数（a，b）的步骤如下：
（1）用a除以b（a2b），得a÷b=q..n（0≤n）。
（2）若rn=0，则（a，b）=b；
（3）若r10，则再用b除以n，得b÷n=q..2（0sr2）
（4）若r2=0，则（a，b）=rn；若r20，则继续用r1除以r2，.…，如此下去，直到能整除为止。
其最后一个余数为0的除数即为（a，b）的最大公约数。
㈣ c语言编程：从键盘输入两个数，求它们的最小公倍数
main()
{
int p,r,n,m,temp;
printf("Please enter 2 numbers n,m:");
scanf("%d,%d",&n,&m);//输入两个正整数.
if(n<m)//把大数放在n中,把小数放在m中.
{temp=n;
n=m;
m=temp;
}
p=n*m;//P是原来两个数n,m的乘积.
while(m!=0)//求两个数n,m的最大公约数.
{
r=n%m;
n=m;
m=r;
}
printf("Its MAXGongYueShu:%d\n",n);//打印最大公约数.
printf("Its MINGongBeiShu:%d\n",p/n);打印最小公倍数.
基本原理如下：
用欧几里德算法（辗转相除法）求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
例如求1515和600的最大公约数，
第一次：用600除1515，商2余315；
第二次：用315除600，商1余285；
第三次：用285除315，商1余30；
第四次：用30除285，商9余15；
第五次：用15除30，商2余0。
1515和600的最大公约数是15。
两个正整数的最小公倍数=两个数的乘积÷两个数的最大公约数
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。这就是说，求两个数的最小公倍数，可以先求出两个数的最大公约数，再用这两个数的最大公约数去除这两个数的积，所得的商就是两个数的最小公倍数。
例 求105和42的最小公倍数。
因为105和42的最大公约数是21，
105和42的积是4410，4410÷21＝210，
所以，105和42的最小公倍数是210。
㈤ c语言如何求最小公倍数和最大公约数
解题步骤：
1、求最大公约数
对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
2、求最小公倍数
对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。
//穷举法求两数的最大公约数
int divisor(int a,int b)
{
int temp;//定义义整型变量
temp=(a>b)?b:a;//采种条件运算表达式求出两个数中的最小值
while(temp>0){
if(a%temp==0&&b%temp==0)//只要找到一个数能同时被a,b所整除，则中止循环
break;
temp--;//如不满足if条件则变量自减，直到能被a,b所整除
}
return temp;//返回满足条件的数到主调函数处
}
//穷举法求两数的最小公倍数
int multiple(int a,int b)
{
int p,q,temp;
p=(a>b)?a:b;//求两个数中的最大值
q=(a>b)?b:a;//求两个数中的最小值
temp=p;//最大值赋给p为变量自增作准备
while(1){//利用循环语句来求满足条件的数值
if(p%q==0)
break;//只要找到变量的和数能被a或b所整除，则中止循环
p+=temp;//如果条件不满足则变量自身相加
}
return p;
}
(5)最小公倍数算法c语言扩展阅读：
用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法一有如下三种：
（1）顺序列举是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。
（2）排列列举有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。
（3）组合列举当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。
例子如下：在公元五世纪我国数学家张丘建在其《算经》一书中提出了“百鸡问题”：
“鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、母、雏各几何？”这个数学问题的数学方程可列出如下：
Cock+Hen+Chick=100
Cock*5+Hen*3+Chick/3=100
显然这是个不定方程，适用于穷举法求解。依次取Cock值域中的一个值，然后求其他两个数，满足条件就是解。
该问题的C语言程序算法如下：
int Cock,Hen,Chick;/*定义公鸡，母鸡，鸡雏三个变量*/
Cock=0;
while(Cock<=19)/*公鸡最多不可能大于19*/
{Hen=0;
whlie(Hen<=33)/*母鸡最多不可能大于33*/
{Chick=100-Cock-Hen;
if(Cock*15+Hen*9+Chick==300)/*为了方便，将数量放大三倍比较*/
printf(" 公鸡=%d 母鸡=%d 雏鸡=%d",Cock,Hen,Chick);
Hen=Hen+1;
}
Cock=Cock+1;
}
㈥ c语言求最小公倍数
1、首先介绍一下求最小公倍数的经典方法:
辗转相除法
有两整数a和b：
①a%b得余数c
②若c=0，则b即为两数的最大公约数
③若c≠0，则a=b，b=c，再回去执行①
a*b除以最大公约数等于最小公倍数
2、因此原问题也化为最小公倍数和最大公约数一起求了。程序的算法如下：
#include<stdio.h>
int lowest_common_multiple(int m,int n);
int main()
{
int m,n,c;
printf("请输入m的值: ");
scanf("%d",&m);
printf("请输入n的值: ");
scanf("%d",&n);
c=lowest_common_multiple( m, n);
printf("请输出最小公倍数c的值: ");
printf("%d ",c);
return 0;
}
int lowest_common_multiple(int m,int n)
{
int remainder,m1,n1;
m1=m;
n1=n;
while (n != 0) {
remainder = m % n;
m = n;
n = remainder;
}
//printf("输出最大公约数m: %d ", m); //此时的m为最大公约数
return m1*n1/m;
}
3、程序的输出如下：
4、此题注释的哪一个是输出最大公约数的。
㈦ C语言编程中最小公倍数怎么求
思想：输入的两个数，大数m是小数n的倍数，那么大数m即为所求的最小公倍数；若大数m不能被小数n整除则需要寻找一个能同时被两数整除的自然数。
从大数m开始依次向后递增直到找到第一个能同时被两数整除的数为止，所以循环变量i的初值为寻找第一个能同时被两整数整除的自然数，并将其输出。需要注意的是，在找到第一个满足条件的i值后，循环没必要继续下去，所以用break来结束循环。
#include<stdio.h>
int main()
{
int m, n, temp, i;
printf("Input m & n:");
scanf("%d%d", &m, &n);
if(m<n) /*比较大小，使得m中存储大数，n中存储小数*/
{
temp = m;
m = n;
n = temp;
}
for(i=m; i>0; i++) /*从大数开始寻找满足条件的自然数*/
if(i%m==0 && i%n==0)
{/*输出满足条件的自然数并结束循环*/
printf("The LCW of %d and %d is: %d ", m, n, i);
break;
}
return 0;
}
(7)最小公倍数算法c语言扩展阅读：
c语言书写规则：
1、一个说明或一个语句占一行。
2、用{} 括起来的部分，通常表示了程序的某一层次结构。{}一般与该结构语句的第一个字母对齐，并单独占一行。
3、低一层次的语句或说明可比高一层次的语句或说明缩进若干格后书写。以便看起来更加清晰，增加程序的可读性。在编程时应力求遵循这些规则，以养成良好的编程风格。
网络-c语言
㈧ C语言编程，求最小公倍数。
1、首先介绍一下求最小公倍数的经典方法:
辗转相除法
有两整数a和b：
①a%b得余数c
②若c=0，则b即为两数的最大公约数
③若c≠0，则a=b，b=c，再回去执行①
a*b除以最大公约数等于最小公倍数
2、因此原问题也化为最小公倍数和最大公约数一起求了。程序的算法如下：
#include<stdio.h>
int lowest_common_multiple(int m,int n);
int main()
{
int m,n,c;
printf("请输入m的值: ");
scanf("%d",&m);
printf("请输入n的值: ");
scanf("%d",&n);
c=lowest_common_multiple( m, n);
printf("请输出最小公倍数c的值: ");
printf("%d ",c);
return 0;
}
int lowest_common_multiple(int m,int n)
{
int remainder,m1,n1;
m1=m;
n1=n;
while (n != 0) {
remainder = m % n;
m = n;
n = remainder;
}
//printf("输出最大公约数m: %d ", m); //此时的m为最大公约数
return m1*n1/m;
}
3、程序的输出如下：
4、此题注释的哪一个是输出最大公约数的。
㈨ c语言如何求最大公约数和最小公倍数
#include <stdio.h>
int main()
{
int a,b,c,m,t;
printf("请输入两个数: ");
scanf("%d%d",&a,&b);
if(a<b)
{
t=a;
a=b;
b=t;
}
m=a*b;
c=a%b;
while(c!=0)
{
a=b;
b=c;
c=a%b;
}
printf("最大公约数是: %d ",b);
printf("最小公倍数是: %d ",m/b);
}
(9)最小公倍数算法c语言扩展阅读
算法思想
利用格式输入语句将输入的两个数分别赋给 a 和 b，然后判断 a 和 b 的关系，如果 a 小于 b，则利用中间变量 t 将其互换。
再利用辗转相除法求出最大公约数，进而求出最小公倍数。最后用格式输出语句将其输出。
#include<stdio.h>是在程序编译之前要处理的内容，称为编译预处理命令。编译预处理命令还有很多，它们都以“#”开头，并且不用分号结尾，所以是c语言的程序语句。
㈩ 最小公倍数怎么求算法c语言
求两个正整数的最小公倍数，可以有很多种不同的计算方法。其中下面是一种用C语言实现的计算方法。
int gcd(int a,int b)
{int r;
while(b)
r=a%b,a=b,b=r;
return a;
}