185937人阅读
最小公倍数：数论中的一种概念，两个整数公有的倍数成为他们的公倍数，其中一个最小的公倍数是他们的最小公倍数，同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数，维基百科：定义
求最小公倍数算法：
最小公倍数=两整数的乘积÷最大公约数
求最大公约数算法：
(1)辗转相除法
有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
例如求27和15的最大公约数过程为：
27÷15 余1215÷12余312÷3余0因此，3即为最大公约数
#include&stdio.h&
void main()
辗转相除法求最大公约数 */
int m, n, a, b, t,
printf(&Input two integer numbers:\n&);
scanf(&%d%d&, &a, &b);
while(b!=0)
/* 余数不为0，继续相除，直到余数为0 */
{ c=a%b; a=b;
printf(&The largest common divisor:%d\n&, a);
printf(&The least common multiple:%d\n&, m*n/a);
有两整数a和b：
① 若a&b，则a=a-b
② 若a&b，则b=b-a
③ 若a=b，则a（或b）即为两数的最大公约数
④ 若a≠b，则再回去执行①
例如求27和15的最大公约数过程为：
27－15＝12( 15&12 ) 15－12＝3( 12&3 )
12－3＝9( 9&3 ) 9－3＝6( 6&3 )
6－3＝3( 3==3 )
因此，3即为最大公约数
#include&stdio.h&
void main ( )
/* 相减法求最大公约数 */
int m, n, a, b,
printf(&Input two integer numbers:\n&);
scanf (&%d,%d&, &a, &b);m=a; n=b;
/* a, b不相等，大数减小数，直到相等为止。*/
while ( a!=b)
printf(&The largest common divisor:%d\n&, a);
printf(&The least common multiple:%d\n&, m*n/a);
有两整数a和b：
② 若a，b能同时被i整除，则t＝i
③ i++
④ 若 i &= a(或b)，则再回去执行②
⑤ 若 i & a(或b)，则t即为最大公约数，结束
① i= a(或b)
② 若a，b能同时被i整除，则i即为最大公约数，
③ i--，再回去执行②
有两整数a和b：
② 若a，b能同时被i整除，则t＝i
③ i++
④ 若 i &= a(或b)，则再回去执行②
⑤ 若 i & a(或b)，则t即为最大公约数，结束
① i= a(或b)
② 若a，b能同时被i整除，则i即为最大公约数，
③ i--，再回去执行②
#include&stdio.h&
void main ()
/* 穷举法求最大公约数 */
m, n, a, b, i,
printf(&Input two integer numbers:\n&);
scanf (&%d,%d&, &a, &b);m=a;
for (i=1; i&= i++)
if ( a%i == 0 && b%i ==0 )
printf(&The largest common divisor:%d\n&, t);
printf(&The least common multiple:%d\n&, m*n/t);
for (t= t&0; t-- )
if ( a%t == 0 && b%t ==0 )
//穷举法求最小公倍数
for (i= ; i++ )
if ( i % a == 0 && i % b ==0 )
printf(&The least common multiple:%d\n&, i )
//多个数的最大公约数和最小公倍数
for (i= i&0; i-- )
if (a%i==0&&b%i==0&&c%i==0)
printf(&The largest common divisor:%d\n&, i);
for (i= ; i++ )
if (i%a==0&&i%b==0&&i% c==0)
printf(&The least common multiple:%d\n&, i )
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：241534次
排名：千里之外
原创：14篇
评论：22条欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 69712 人关注过本帖
标题：C语言怎么求最大公约数和最小公倍数
等　级：论坛游侠
帖　子：137
专家分：134
结帖率：100%
&&问题点数：0&&回复次数：26&&&
C语言怎么求最大公约数和最小公倍数
只会用笔算算。。写程序实在不会。。会的麻烦写下思路
搜索更多相关主题的帖子:
等　级：论坛游侠
帖　子：89
专家分：124
求a,b（a&b）的最大公约数c
c满足 (a-b),b的最大公约数=c
然后再把较大的数减较小的数。。。最后的就是最大公约数了。。。
a,b的最小共倍数 求出最大公约数c以后 a*b/c就是。。。
等　级：论坛游民
帖　子：21
专家分：10
输入两个正整数m和n, 求其最大公约数和最小公倍数. &1& 用辗转相除法求最大公约数 算法描述: m对n求余为a, 若a不等于0 则 m &- n, n &- a, 继续求余 否则 n 为最大公约数 &2& 最小公倍数 = 两个数的积 / 最大公约数
#include int main()
&int m, int m_cup, n_cup, /*被除数, 除数, 余数*/
&printf(&Enter two integer:\n&);
&scanf(&%d %d&, &m, &n);
&if (m & 0 && n &0)
&&& m_cup =
&&& n_cup =
&&& res = m_cup % n_
&&& while (res != 0)
&&&&&& m_cup = n_
&&&&&& n_cup =
&&&&&& res = m_cup % n_
&&&&&printf(&Greatest common divisor: %d\n&, n_cup);
&&&&&printf(&Lease common multiple : %d\n&, m * n / n_cup);
&&else printf(&Error!\n&);
&&return 0;
★ 关于辗转相除法, 搜了一下, 在我国古代的《九章算术》中就有记载，现摘录如下: 约分术曰：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。 辗转相除法求最大公约数，是一种比较好的方法，比较快。 对于5两个数，你能迅速地求出它们的最大公约数吗？一般来说你会找一找公共的使因子，这题可麻烦了，不好找，质因子大。 现在教你用辗转相除法来求最大公约数。 先用较大的75569除以52317，得商1，余数23252，再以52317除以23252，得商2，余数是5813，再用23252做被除数，5813做除数，正好除尽得商数4。这样5813就是7的最大公约数。你要是用分解使因数的办法，肯定找不到。 那么，这辗转相除法为什么能得到最大公约数呢？下面我就给大伙谈谈。 比如说有要求a、b两个整数的最大公约数，a＞b，那么我们先用a除以b，得到商8，余数r1：a÷b＝q1…r1我们当然也可以把上面这个式子改写成乘法式：a＝bq1＋r1------l） 如果r1＝0，那么b就是a、b的最大公约数3。要是r1≠0，就继续除，用b除以r1，我们也可以有和上面一样的式子： b＝r1q2＋r2-------2） 如果余数r2＝0，那么r1就是所求的最大公约数3。为什么呢？因为如果2）式变成了b＝r1q2，那么b1r1的公约数就一定是a1b的公约数。这是因为一个数能同时除尽b和r1，那么由l）式，就一定能整除a，从而也是a1b的公约数。 反过来，如果一个数d，能同时整除a1b，那么由1）式，也一定能整除r1，从而也有d是b1r1的公约数。 这样，a和b的公约数与b和r1的公约数完全一样，那么这两对的最大公约数也一定相同。那b1r1的最大公约数，在r1＝0时，不就是r1吗？所以a和b的最大公约数也是r1了。 有人会说，那r2不等于0怎么办？那当然是继续往下做，用r1除以r2，……直到余数为零为止。 在这种方法里，先做除数的，后一步就成了被除数，这就是辗转相除法名字的来历吧。
等　级：侠之大者
帖　子：212
专家分：455
求a,b（a&b）的最大公约数c
c满足 (a-b),b的最大公约数=c
然后再把较大的数减较小的数。。。最后的就是最大公约数了。。。
最小公倍数 a*b/c
等　级：论坛游侠
帖　子：137
专家分：134
以下是引用已屏蔽在 20:29:35的发言：
求a,b（a&b）的最大公约数c
c满足 (a-b),b的最大公约数=c
然后再把较大的数减较小的数。。。最后的就是最大公约数了。。。
a,b的最小共倍数 求出最大公约数c以后 a*b/c就是。。。2楼意思是。。。。假如a=5,b=3
c满足(5-3),b
然后b-（5-3） 就是最大公约数了？&&
等　级：论坛游侠
帖　子：137
专家分：134
没高手教教？
等　级：论坛游侠
帖　子：89
专家分：124
开始&&& a=5,b=3&&&假设对a,b大小关系不要求
第一次&&a=5-3=2,b=3
第二次&&a=2,b=3-2=1
2可以被1整除了，所以1就是3和5的最大公约数
啊，好像3楼说的对用取余好点
等　级：论坛游侠
帖　子：137
专家分：134
求最大公约数这东西好复杂。。都说什么辗转相除的 看不懂
等　级：侠之大者
帖　子：114
专家分：436
看看这个网址的讲解就知道了讲的挺细的，也简单 /StBlogPageMain/Efp_BlogLogSee.aspx?cBlogLog=
等　级：侠之大者
帖　子：160
专家分：471
int gcd（int m,int n)
if(m%n==0) printf(&%d\n&,n);
gcd(n,m%n);
版权所有，并保留所有权利。
Powered by , Processed in 0.021238 second(s), 8 queries.
Copyright&, BCCN.NET, All Rights Reserved求三个数的最大公约数和最小公倍数的方法--《小学教学研究》1992年10期
求三个数的最大公约数和最小公倍数的方法
【摘要】：正 (Ⅰ)求最大公约数①三个数的公约数只有1,它们的最大公约数,就是1。②较小数分别是其他两个数的约数,它们的最大公约数就是这个较小数。③把较小数缩小至其他两个数的约数为止,那么缩小后的数就是原三个数的最大公约数。④短除法: A.除数,只三不二(只能用三个数的公约数,不能用两个数的公约数)。 B.商除至三个数的公约数只有1为止。 C.所有除数相乘积,就是它们的最大公约数。
【作者单位】：
【关键词】：
【正文快照】：
(!)求最大公约数 ①三个数的公约数只有1,它们的最大公约数,就是1。 ②较小数分别是其他两个数的约数,它们的最大公约数就是这个较小数。 ③把较小数缩小至其他两个数的约数为止,那么缩小后的数就是原三个数的最大公约数。 ④海脸法; A。除数,只三不二(只能用三个数的公约数,
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
陈任科;周积福;;[J];小学教学研究;1994年09期
赵佑忠;;[J];小学教学研究;1986年03期
骆瑞霞;[J];河北教育;1995年12期
邱廷建;;[J];云南教育(基础教育版);2006年04期
张展志;;[J];小学教学研究;1986年06期
冯惠民;[J];小学教学参考;1998年01期
孙凤霞;;[J];小学教学设计;2006年08期
邱廷建;;[J];小学教学参考;2006年08期
王丽端;;[J];云南教育(基础教育版);1991年Z1期
曲海全;;[J];中小学教学研究;2008年08期
中国重要会议论文全文数据库
郎玺慧;李永武;郎希新;;[A];中国珠算心算协会学术研究专业委员会2010年年会暨理论研讨会论文集[C];2010年
中国重要报纸全文数据库
盘县柏果镇朝阳小学
黄兴;[N];六盘水日报;2008年
常州市武进区卢家巷实验学校
沈丹萍;[N];江苏教育报;2010年
谭丽萍;[N];六盘水日报;2008年
漯河市临颍县王岗镇葛家学校
张书远;[N];学知报;2011年
北辰区小淀小学校长 赵占凤;[N];天津教育报;2010年
王林珍;[N];海南农垦报;2007年
陈晓静（作者单位：市油管道三小）;[N];廊坊日报;2006年
徐大来;[N];中国教育报;2004年
常州市新北区汤庄桥小学 许红卫;[N];江苏教育报;2009年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号