最小公倍数c语言算法

⑴ 最小公倍数怎么求算法c语言

求两个正整数的最小公倍数，可以有很多种不同的计算方法。其中下面是一种用C语言实现的计算方法。
int gcd(int a,int b)
{int r;
while(b)
r=a%b,a=b,b=r;
return a;
}

⑵ c语言输入三个数求最小公倍数算法

先求两个的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数

#include<stdio.h>
intgcd(inta,intb)
{
return!b?a:gcd(b,a%b);
}
intlcm(inta,intb)
{
returna/gcd(a,b)*b;
}
intmain()
{
inta,b,c;
scanf("%d%d%d",&a,&b,&c);
printf("%d
",lcm(lcm(a,b),c));
return0;
}

⑶ 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;

}

(3)最小公倍数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语言编写程序求两个数的最小公倍数,并输出

如图使用辗转相除法求最小公倍数：

(4)最小公倍数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语言中，求两个数的最小公倍数，的“高效”算法是

这思路我自己想的，但是我也说不太明白，反正我知道怎么回事
1先判断大数%小数是不是0，是0那么大数就是最小公倍数
2不是的话，让大数%小数得到一个数，让小数%得到的数，如果得0
那么让大数*（小数/(大数%小数)）,得到得数是最小公倍数
3如果2中小数%得到的这个数不等于0，那么恭喜你，这两个数的最小公倍数就是：大数*小数
4如果这两个数相等，那么，随便一个都是最小公倍数
纯手打，今天刚好做这个题，看到网上没什么答案，我就写写我的思路
C++语法如下：
int pd(int A,int B);
int main() {int i, k;goto C;
C: {
printf("第一个数："); scanf("%d", &i);
printf("第二个数："); scanf("%d", &k);
printf("这两个数的公倍数为：%d\n\n", pd(i, k));
goto C; }
return 0;
}
int pd(int A, int B) {
int P;
if (A > B) {
if (A%B == 0) { P = A; }
else if (B % (A%B) == 0) { P = A*(B / (A%B)); }
else { P = A*B; }
}
else if (B > A) {
if (B%A == 0) { P = B; }
else if (A % (B%A) == 0) { P = B*(A / (B%A)); }
else { P = B*A; }
}
else { P = A; }
return P;
}

⑹ 最大公约数和最小公倍数c语言算法

#include <stdio.h>

int gcd(int x ,int y)

{ int r;

for(;r=x%y;)x=y,y=r;

return y;

}

int main()

{ int a,b,c;

scanf("%d%d",&a,&b);

c=gcd(a,b);

printf("%d %d ",c,a*b/c);

return 0;

}

⑺ C语言求n个数的最小公倍数

你输入的n是1吧，当你输入1时，程序运行到for语句时，i的初值为1，由于条件判断语句1<1不满足，所以for语句根本就没有执行。你精心设计最大公约数函数不仅没有执行，甚至y也没有被赋值。程序直接转到printf语句。直接输出的就是x，也就是你说的输入的第一个数。由于程序使用了while语句，所以该程序不会自行结束。仍会等待你重新输入n进行下一轮计算。

解决方法：在for语句i初始值由1改为0，即i=0,或程序运行时，n值你直接输入2，但for循环只执行一次，然后依次输入x，y的值。ps:其实你的程序，运行没有错，算法设计的不是很好。我是把i改成0了。运行结果如图。

⑻ 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;

}

(8)最小公倍数c语言算法扩展阅读：

c语言书写规则：

1、一个说明或一个语句占一行。

2、用{} 括起来的部分，通常表示了程序的某一层次结构。{}一般与该结构语句的第一个字母对齐，并单独占一行。

3、低一层次的语句或说明可比高一层次的语句或说明缩进若干格后书写。以便看起来更加清晰，增加程序的可读性。在编程时应力求遵循这些规则，以养成良好的编程风格。

网络-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语言求最小公倍数

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、此题注释的哪一个是输出最大公约数的。