c语言求最大公约数c语言求两个数的最大公约数

c语言求最大公约数  时间:2021-07-30  阅读:()

C语言中求最大公约数的函数

#include "stdio.h" int main() { int d1,d2,r; printf("输入两数:"); scanf("%d %d",&d1,&d2); do { r=d1%d2; d1=d2;d2=r; }while(d2!=0); printf("最大公约数是:%d",d1); } //递归法 #include "stdio.h" int fun(int d1,int d2) { if(d2!=0) return fun(d2,d1%d2); else return d1; } int main() { int d1,d2; printf("输入两个正整数:"); scanf("%d %d",&d1,&d2); printf("最大公约数是:%d",fun(d1,d2)); }

如何用C语言求两个数的最大公约数的三种算法

1、相减法 #include<stdio.h> int main() { int a,b; int c=0;//计数器 while(1)//循环判断的作用 { printf("输入两个数字求最大公约数:"); scanf("%d%d",&a,&b); while(a!=b) { if(a>b) a=a-b; else b=b-a; c++; } printf("最大公约数是:%d ",a); printf("%d ",c); } return 0; } 运行效果: 2、辗转相除法: #include<stdio.h> int a,b,temp; int Division(){ printf("请输入两个数(a,b): "); scanf("%d,%d",&a,&b); if(a<b){ temp=a; a=b; b=temp; } while(a%b!=0){ temp=a%b; a=b; b=temp; } printf("最大公约数为:%d ",b); return 0; } 3、穷举法 #include<stdio.h> int main() { int a,b,c; int d=0;//计数器 while(1) { printf("输入两个数字求最大公约数:"); scanf("%d%d",&a,&b); c=(a>b)?b:a;//三目运算符 while(a%c!=0||b%c!=0) { c--; d++; } printf("最大公约数是:%d ",c); printf("%d ",d); } return 0; }

求最大公约数和最小公倍数用c语言

输入两个正整数m和n, 求其最大公约数和最小公倍数. <1> 用辗转相除法求最大公约数 算法描述: m对n求余为a, 若a不等于0 则 m <- n, n <- a, 继续求余 否则 n 为最大公约数 <2> 最小公倍数 = 两个数的积 / 最大公约数 #include int main() { int m, n; int m_cup, n_cup, res; /*被除数, 除数, 余数*/ printf("Enter two integer: "); scanf("%d %d", &m, &n); if (m > 0 && n >0) { m_cup = m; n_cup = n; res = m_cup % n_cup; while (res != 0) { m_cup = n_cup; n_cup = res; res = m_cup % n_cup; } printf("mon divisor: %d ", n_cup); printf("mon multiple : %d ", m * n / n_cup); } else printf("Error! "); return 0; } ★ 关于辗转相除法, 搜了一下, 在我国古代的《九章算术》中就有记载,现摘录如下: 约分术曰:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。

以等数约之。

” 其中所说的“等数”,就是最大公约数。

求“等数”的办法是“更相减损”法,实际上就是辗转相除法。

辗转相除法求最大公约数,是一种比较好的方法,比较快。

对于52317和75569两个数,你能迅速地求出它们的最大公约数吗?一般来说你会找一找公共的使因子,这题可麻烦了,不好找,质因子大。

现在教你用辗转相除法来求最大公约数。

先用较大的75569除以52317,得商1,余数23252,再以52317除以23252,得商2,余数是5813,再用23252做被除数,5813做除数,正好除尽得商数4。

这样5813就是75569和52317的最大公约数。

你要是用分解使因数的办法,肯定找不到。

那么,这辗转相除法为什么能得到最大公约数呢?下面我就给大伙谈谈。

比如说有要求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,……直到余数为零为止

C语言程序:求两个数的最大公约数?

#include "stdio.h" main() { int x,y,i,gy,m; int s=1; printf("输入两个数: "); scanf("%d",&x); scanf("%d",&y); do { if(x>y) { m=y; } else { m=x; } for(i=2;i<=m;i++) { if(x%i==0&&y%i==0) { x=x/i; y=y/i; s=s*i; break; } } }while(i<m); gy=s;

printf("公约数为%d ",gy); }

c语言求两个数的最大公约数

#include <stdio.h> void main() { int m,n,a,b; int r; printf("请输入m,n: "); scanf("%d,%d",&m,&n); if(m>=n) a=m,b=n; else a=n,b=m; r=a%b; while(r!=0) { a=b; b=r; r=a%b; } printf("最大公约数是: %d ",b); } 楼上的int abc(int x,int y); int edf(int x,int y); 是自定义函数 估计你还没有学到吧 其实用一个循环+“辗转相除法” 就行了 去年学的,学艺不精 望采纳,谢谢!!

博鳌云¥799/月,香港110Mbps(含10M CN2)大带宽独立服务器/E3/8G内存/240G/500G SSD或1T HDD

博鳌云是一家以海外互联网基础业务为主的高新技术企业,运营全球高品质数据中心业务。自2008年开始为用户提供服务,距今11年,在国人商家中来说非常老牌。致力于为中国用户提供域名注册(国外接口)、免费虚拟主机、香港虚拟主机、VPS云主机和香港、台湾、马来西亚等地服务器租用服务,各类网络应用解決方案等领域的专业网络数据服务。商家支持支付宝、微信、银行转账等付款方式。目前香港有一款特价独立服务器正在促销,...

收到几个新商家投稿(HostMem,无忧云,青云互联,TTcloud,亚洲云端,趣米云),一起发布排名不分先后

7月份已经过去了一半,炎热的夏季已经来临了,主机圈也开始了大量的夏季促销攻势,近期收到一些商家投稿信息,提供欧美或者亚洲地区主机产品,价格优惠,这里做一个汇总,方便大家参考,排名不分先后,以邮件顺序,少部分因为促销具有一定的时效性,价格已经恢复故暂未列出。HostMem部落曾经分享过一次Hostmem的信息,这是一家提供动态云和经典云的国人VPS商家,其中动态云硬件按小时计费,流量按需使用;而经典...

PIGYun中秋特惠:香港/韩国VPS月付14元起

PIGYun发布了九月份及中秋节特惠活动,提供8折优惠码,本月商家主推中国香港和韩国机房,优惠后最低韩国每月14元/中国香港每月19元起。这是一家成立于2019年的国人商家,提供中国香港、韩国和美国等地区机房VPS主机,基于KVM架构,采用SSD硬盘,CN2+BGP线路(美国为CUVIP-AS9929、GIA等)。下面列出两款主机配置信息。机房:中国香港CPU:1core内存:1GB硬盘:10GB...

c语言求最大公约数为你推荐
word2003公式编辑器w2003的公式编辑器在那win7无线局域网win7怎么建立无线局域网联机玩游戏?goalgoalgoal开头是O后面是lei什么的英语歌,男声的,好像是摇滚~~~百度预测世界杯世界杯,今晚预测...微软将停止支持32位Win10系统微软即将停止支持当前操作系统,如果不升级会怎么样iphone12或支持北斗导航苹果12处理器是什么微信语音在哪个文件夹【求助】微信语音的文件夹在哪里??催收软件哪个好靠谱的催收方式除了正规要账公司,还有哪些渠道的?智能公共广播系统智能广播的系统内容腾讯汽车论坛买车需要注意些神马?
中文域名注册 工信部域名备案 新网域名管理 inmotionhosting jsp主机 linode gateone 名片模板psd 免空 国外代理服务器软件 福建铁通 中国电信宽带测速网 电信主机 华为k3 中国联通宽带测速 空间服务器 免费个人网页 江苏徐州移动 美国主机侦探 cx域名 更多