计算机编程求最大公约数与最小公倍数，这是一个常见的简单算法
我的图书馆
计算机编程求最大公约数与最小公倍数，这是一个常见的简单算法
计算最大公约数和最小公倍数是简单常见的算法，他有多种方式实现，比如：穷举法、辗转相除法、相减法等等，方法很多，目的相同，下面就用其中一种方法，辗转相除法来完成这个算法，下面将用计算机编程的方式实现。9和15最大公约数为3最大公约数和最小公倍数的概念最大公约数指某几个整数共有约数中最大的一个。最小公倍数是某几个整数公有的倍数中最小的一个正整数。它们之间的关系最大公约数=两数之积/最小公倍数，所以只要求出一个另外一个自然通过简单的计算求出来了。辗转相除法，算法举例有两整数a和b：① a%b得余数c② 若c=0，则b即为两数的最大公约数③ 若c≠0，则a=b，b=c，再回去执行①例如求35和15的最大公约数过程为：35÷15 余5，,15÷5余0，5即为最大公约数代码实现图片代码演示结果结果文本代码import java.util.Spublic class S {public static void main(String args[]){Scanner s=new Scanner(System.in);int a=s.nextInt();int b=s.nextInt();int m=a;//用m记录aint n=b;//用n记录bint c=1;//定义余数while(c!=0){//只要余数不等于0，就做循环c=a%b;a=b;b=c;System.out.println(a+b+c);}System.out.println('最大公约数'+a);//此时的a是原来的bSystem.out.println('最小公倍数数'+m*n/a);//利用关系计算出最小公倍数}}结语至此这个算法就演示完毕了，当然实现的方法好多，效率也不一样，这里只演示了一种算法，有兴趣的可以试试其他方法。每天持续分享计算机编程知识，c语言，java，php等等，欢迎交流，一起进步，欢迎收藏，转发，关注趣IT科技，喜欢就请点个赞吧。本文为头条号作者发布，不代表今日头条立场。
馆藏&55680
TA的最新馆藏
喜欢该文的人也喜欢近日，《辉煌中国》在央视热播，广大人民群众反响强烈。国家的飞速发展让我们感到骄傲和自豪，祖国为世界和平作出的巨大贡献让我们深感荣幸。这个国庆长假，焦点不应只放在“八天”。别忘了享受和平年代繁荣昌盛的同时，去看看《辉煌中国》，感受这部让我们热血沸腾的纪录片。
在此可输入您对该资料的评论~
(window.slotbydup = window.slotbydup || []).push({
id: '4540180',
container: s,
size: '250,200',
display: 'inlay-fix'
热门资料排行
添加成功至
资料评价：
所需积分：0欢迎加入我们，一同切磋技术。 &
用户名： &&&
密　码： &
共有 76327 人关注过本帖
标题：C语言怎么求最大公约数和最小公倍数
等　级：论坛游侠
帖　子：137
专家分：134
结帖率：100%
&&问题点数：0&&回复次数：28&&&
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.073330 second(s), 7 queries.
Copyright&, BCCN.NET, All Rights Reserved如果要求两个正整数的最小公倍数和最大公约数,请用程序流程图,N-S图,PAD图分别表示出求解该问题的算法
如果要求两个正整数的最小公倍数和最大公约数,请用程序流程图,N-S图,PAD图分别表示出求解该问题的算法
C语言是Combined√anguage（组合语言）的中英混合简称.是一种计算机程序设计语言.它既具有高级语言的特点6又具有汇编语言的特点ol希望帮到你吧.
与《如果要求两个正整数的最小公倍数和最大公约数,请用程序流程图,N-S图,PAD图分别表示出求解该问题的算法》相关的作业问题
#includeint gcd(int m,int n)//最大公约数{if(m 再问： t = n,n = m,m = if(n == 0) else return gcd(n,m%n); 求解释。还有return m*n/gcd(m,n); while(scanf("%d %d
'最大公约数Function getGcd(num1 As Long, num2 As Long) As Long Dim i As Long For i = IIf(num1 < num2, num1, num2) To 1 Step -1 If num1 Mod i = 0 And num2 Mod i = 0 T
Private Sub Command1_Click() Dim k%,a%,b%,c%a = Val(Text1)b = Val(Text2)If (a Mod 2 = 0) And (b Mod 2 = 0) Thena = a \ 2b = b \ 2k = 2Elsek = 1End IfIf a < b Th
#include "iostream"int getMin(int m,int n)//最小公倍数{&&& int i,j;&&& i=m;&&& if(n&i)&&nbsp
用短除法先分别把两个数用短除法除出来再把得数中一样的相乘就可以了例如：42=2*3*7 30=2*3*5那么它们的最大公因数就是2*3=6
#include&&iostream&using&std::using&std::using&std::void&swap(int&*x,int&*y),Difference(int&n1,int&n
辗转相除法：设两数为a、b(b＜a),求它们最大公约数(a、b)的步骤如下：用b除a,得a＝bq.r 1(0≤r).若r1=0,则(a,b)＝b；若r1≠0,则再用r1除b,得b＝r1q.r2 (0≤r2).若r2＝0,则(a,b)＝r1,若r2≠0,则继续用r2除r1,……如此下去,直到能整除为止.其最后一个非零余数
//求解两个数最大公约数问题#includeunsigned int gongYueShu(unsigned M,unsigned N){\x05\x05while(N!=0)\x05{r=M%N;\x05\x05M=N;\x05\x05N=r;\
设为ab 和ac （b,c）=1且b>c则 abc-a=ab=acbc-1=b+cb=(c+1)/(c-1) b=1+2/(c-1) 都是自然数且b>c所以 b=3 c=2 而a(b+c)=40 所以a=8 即16和24
设两个合数的最大公约数分别是n,则这两个合数分别为an和bn（a和b互质）他们的最小公倍数就是abn得方程n+abn=143n(1+ab)=11X13如果n=11,ab=12,a=3,b=4.这两个数分别为33和44；如果n=13,ab=10,a=2,b=5.这两个数分别为26和65.
数组a没有定义. 再问： 定义了，在第八行 再答： 错了，把数组a的定义放在最前面试一试。再问： 这个前后不关紧要吧 再答： 还有第一个scanf中，改为&a[i][j] 再答： 如果你学的是纯C语言，不允许在代码中间定义，定义语句需要放在最前面。 再答： 如果是C++兼容性C语言，那就不用关心定义在哪里，用之前定义就
设最大公约数是X 最小公倍数是YY=6*XX+Y=49 则X=7 Y=4242的两位数约数只有14 21 42 所以两个数是 21 14
最大公因数是：49÷（6+1）=7最小公倍数是：7×6=42 6=1×6=2×3这两数是：7×1=7,7×6=42或者是：7×2=14,7×3=21
我花了很长的时间的说、亲、给点分呗How time flies!I'm from primary school to junior middle schoolPrimary school when the campus feel greatBy junior high to found the campus is so
#include void main(){int x,y,tempGY,tempGB,GY,GB; printf("输入两个正整数（用空格分开）,求这两个正整数的最小公倍数和最大公约数：\n");scanf("%d%d",&x,&y);for(int i=1;i
因为60 = 1×60 = 2×30 = 3×20 = 4×15 = 5×12 = 6×10两个正整数的最小公倍数是60,则这两个数只可能在以下集合：{1、2、3、4、5、6、10、12、15、20、30、60}而在上述集合中,乘积为300的有如下组合：{5、60}、{10、30}、{15、20}又由于两个数的最小公倍
15、25、45的最小公倍数2的最小公倍数的最小公倍数360最大公约数3
数小就是最大公约,数大就是最小公倍新手园地& & & 硬件问题Linux系统管理Linux网络问题Linux环境编程Linux桌面系统国产LinuxBSD& & & BSD文档中心AIX& & & 新手入门& & & AIX文档中心& & & 资源下载& & & Power高级应用& & & IBM存储AS400Solaris& & & Solaris文档中心HP-UX& & & HP文档中心SCO UNIX& & & SCO文档中心互操作专区IRIXTru64 UNIXMac OS X门户网站运维集群和高可用服务器应用监控和防护虚拟化技术架构设计行业应用和管理服务器及硬件技术& & & 服务器资源下载云计算& & & 云计算文档中心& & & 云计算业界& & & 云计算资源下载存储备份& & & 存储文档中心& & & 存储业界& & & 存储资源下载& & & Symantec技术交流区安全技术网络技术& & & 网络技术文档中心C/C++& & & GUI编程& & & Functional编程内核源码& & & 内核问题移动开发& & & 移动开发技术资料ShellPerlJava& & & Java文档中心PHP& & & php文档中心Python& & & Python文档中心RubyCPU与编译器嵌入式开发驱动开发Web开发VoIP开发技术MySQL& & & MySQL文档中心SybaseOraclePostgreSQLDB2Informix数据仓库与数据挖掘NoSQL技术IT业界新闻与评论IT职业生涯& & & 猎头招聘IT图书与评论& & & CU技术图书大系& & & Linux书友会二手交易下载共享Linux文档专区IT培训与认证& & & 培训交流& & & 认证培训清茶斋投资理财运动地带快乐数码摄影& & & 摄影器材& & & 摄影比赛专区IT爱车族旅游天下站务交流版主会议室博客SNS站务交流区CU活动专区& & & Power活动专区& & & 拍卖交流区频道交流区
白手起家, 积分 5, 距离下一级还需 195 积分
论坛徽章:0
本帖最后由 随缘浮动 于
14:54 编辑
一个求最大公约数和最小公倍数的问题& && && && && && &
这个是别人写的给我查错的我也没发现哪错了
特请指教了
代码如下：
#include &stdio.h&
void main()
{ int i,j,m,n,k=1;
& & & & printf(&请输入两个数: \n&);
& & & & scanf(&%d%d&,&m,&n);
& & & & for(i=1;i&=m;i++)
& & & && &{if(m%i)
& & & && &&&{for(j=1;j&=n;j++)
& & & && & & & & && &{if(n%j)
& & & && & & & & && &&&{if(i==j)
& & & && & & & & && && & & && &&&k*=i;
& & & && & & & & && &&&}
& & & && && & }
& & & && && &}
& & & && & }
& & printf(&最大公约数为: %d\n最小公倍数为: %d\n&,k,m*n/k);
未命名.jpg (29.57 KB, 下载次数: 2)
14:52 上传
QQ截图00.jpg (26.19 KB, 下载次数: 0)
14:54 上传
&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp
丰衣足食, 积分 524, 距离下一级还需 476 积分
论坛徽章:0
看着好难受啊，好吧如果你真的要这么写的话，把m % i和n % j分别改成m % i == 0和n % j == 0，并且把k *= j改成k = j
其他我就不说了，一路走好……
白手起家, 积分 5, 距离下一级还需 195 积分
论坛徽章:0
daybreakcx
别人新手写的，
新手学的有限。
我看不出错就发上来了，
把m % i和n % j分别改成m % i == 0和n % j == 0，
效果都是一样的
& &把k *= j改成k = j
就不是求最大公约数了，只是公约数了，那就错了
白手起家, 积分 5, 距离下一级还需 195 积分
论坛徽章:0
一个简单的问题折腾这么久
家境小康, 积分 1969, 距离下一级还需 31 积分
论坛徽章:9
本帖最后由 w_anthony 于
16:12 编辑
数学老师不会原谅这位新手！
首先“== 0”是需要的，先搞清楚什么叫公约数，再去求最大；
其次如果最大公约数是合数，比如6，那么由于6 = 2 * 3，两层循环的时候2和3已经分别被乘过，到6的时候会再被乘一次，那么这里就有重复；
再次如果最大公约数的质因子里面有两个相同的数，比如9，由于9 = 3 * 3，但是你的循环里面会缺少一个3。
**************************
先不论逻辑真缪，点评，最有喜感的写法：
for(j=1;j&=n;j++)
& & & & {if(i==j)
& & & & & & & & k*=i;
其实不就是想看看n能不能被i整除？既然如此，那么为什么不：
if ((i &= n) && (n % i))
& & & & k *=
这就与“拨电话号码，明知道号码是多少，非要从1开始数号码，数到了再拨”没有什么本质区别……
************************
最大公约数，在数学里面最快的方法是辗转相除法，就算不用辗转相除，一定要用循环，那么可以从两个数的较小者开始，往小方向循环，找到最大公约数。我估计那位新手是从分解因子的代码里面随便抄了一份，不加思考就改出这个“最大公约数”了。
丰衣足食, 积分 524, 距离下一级还需 476 积分
论坛徽章:0
& & 新手不新手的不是问题，本身算法逻辑也没有错，只不过我说的你试过么？没试过你就说不行，好吧，既然你觉得我不对懒得试一下，我帮你改好运行给你看看证明我是对的吧，中文我在C里改了，去大括号我觉得舒坦，个人喜好个人习惯，看不惯就无视代码只看结果吧~~~#include &stdio.h&
int main()
{
& & & & int i, j, m, n, k = 1;
& & & & printf(&Input two numbers : &);
& & & & scanf(&%d%d&, &m, &n);
& & & & for (i = 1; i &= i++)
& & & & & & & & if (m % i == 0)
& & & & & & & & & & & & for (j = 1; j &= j++)
& & & & & & & & & & & & & & & & if (n % j == 0 && i == j)
& & & & & & & & & & & & & & & & & & & & & & & & k =
& & & & printf(&The greatest common divisor is : %d\nThe least common multiple is : %d\n&, k, n * m / k);
& & & & return 0;
}复制代码运行结果：[daybreakcx@Arch ~]$ ./a.out
Input two numbers : 15 24
The greatest common divisor is : 3
The least common multiple is : 120
[daybreakcx@Arch ~]$ ./a.out
Input two numbers : 24 42
The greatest common divisor is : 6
The least common multiple is : 168
[daybreakcx@Arch ~]$ ./a.out
Input two numbers : 1 50
The greatest common divisor is : 1
The least common multiple is : 50
[daybreakcx@Arch ~]$ ./a.out
Input two numbers : 50 1
The greatest common divisor is : 1
The least common multiple is : 50复制代码BTW：直接k = i得到的就是最大公约数，因为最后一次赋值把前面都盖掉了留下最大的，可以说抛开效率而言，这个方法挺巧妙的，但是对于这个方法有一个限制，就是如果其中一个是0得到的结果不对（其中一个是0，根据gcd的定义，得到的结果应该是较大的那个数，但是由于算法的原因得到的是0，虽然这个算法避免了判断辗转相除中除0的可能，却得到了对于我来说错误的结果，好吧，这是我自己的想法，不同意我的定义也无视吧），重申一遍我从来没对你那个什么新手的问题有任何想法，其他我真的不想说了……
丰衣足食, 积分 524, 距离下一级还需 476 积分
论坛徽章:0
重申一次，谁都是从新手过来的，否定新手就是否定自己的努力，但是不动手就永远都是新手，这是我对自己说的，我说完了~~~
丰衣足食, 积分 795, 距离下一级还需 205 积分
论坛徽章:0
这个好像是数学问题吧，而且没记错的话还是初中的吧。 我认为你知道什么是公约数和公倍数，并且所谓的你“会”编程的话，这个问题不难吧？
请无视我所说的一切吧 。 哈哈哈哈哈&&
论坛徽章:2
提示: 作者被禁止或删除 内容自动屏蔽
小富即安, 积分 2875, 距离下一级还需 2125 积分
论坛徽章:7
北京盛拓优讯信息技术有限公司. 版权所有 京ICP备号 北京市公安局海淀分局网监中心备案编号：22
广播电视节目制作经营许可证(京) 字第1234号
中国互联网协会会员&&联系我们：
感谢所有关心和支持过ChinaUnix的朋友们
转载本站内容请注明原作者名及出处}