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); 是自定义函数 估计你还没有学到吧 其实用一个循环+“辗转相除法” 就行了 去年学的,学艺不精 望采纳,谢谢!!

ShineServers(5美元/月)荷兰VPS、阿联酋VPS首月五折/1核1G/50GB硬盘/3TB流量/1Gbps带宽

优惠码50SSDOFF 首月5折50WHTSSD 年付5折15OFF 85折优惠,可循环使用荷兰VPSCPU内存SSD带宽IPv4价格购买1核1G50G1Gbps/3TB1个$ 9.10/月链接2核2G80G1Gbps/5TB1个$ 12.70/月链接2核3G100G1Gbps/7TB1个$ 16.30/月链接3核4G150G1Gbps/10TB1个$ 18.10/月链接阿联酋VPSCPU内存SS...

A400:36元/季,16.8/月kvm架构,线路优质,延迟低

A400互联是一家成立于2020年的商家,主要推行洛杉矶服务器采用kvm架构,线路优质,延迟低,稳定性高!全场产品对标腾讯云轻量,服务器线路有有美国洛杉矶cn2_gia、香港cn2+cmi,目前推行的vps服务器均为精心挑选的优质线路机房,A400互联推出了夏季优惠洛杉矶5折、香港7折促销活动,质量可靠,价格实惠!二:优惠码洛杉矶五折优惠码:20210620香港cn2七折优惠码:0710三、优惠方...

ZJI全新上架香港站群服务器,4C段238个IP月付1400元起

ZJI本月新上线了香港葵湾机房站群服务器,提供4个C段238个IPv4,支持使用8折优惠码,优惠后最低每月1400元起。ZJI是原Wordpress圈知名主机商家:维翔主机,成立于2011年,2018年9月更名为ZJI,提供中国香港、台湾、日本、美国独立服务器(自营/数据中心直营)租用及VDS、虚拟主机空间、域名注册等业务,所选数据中心均为国内普遍访问速度不错的机房。葵湾二型(4C站群)CPU:I...

c语言求最大公约数为你推荐
贺卡网站你觉得专门做网页贺卡的网站怎么样?淘气鸟松鸦是否会说话?angel的意思Angel、的中文意思云图好看吗电影《云图》到底讲的什么,没看懂,高手来说一下。慕课网址如何加入慕课学习课程?魔兽世界密保卡WOW现在的密保卡怎么弄?联通玩电信游戏关于联通到底能不能去电信区玩游戏。。。。pps电影pps电影下载 pps影音下载 pps最新版下载新浪短网址链接生成新浪微博怎么发图文带短连接连接到自己的网站?盈科oa办公系统OA办公设备主要有哪些?该怎样安装和维护、。
免费申请域名和空间 mobaxterm qq数据库下载 免费mysql 北京双线机房 服务器维护方案 佛山高防服务器 免费高速空间 美国免费空间 web服务器搭建 国外在线代理服务器 西安主机 服务器论坛 摩尔庄园注册 umax 博客域名 comodo 热云 电脑主机启动不了 suspended翻译 更多