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

RAKSmart VPS主机半价活动 支持Windows系统 包含香港、日本机房

RAKSmart 商家最近动作还是比较大的,比如他们也在增加云服务器产品,目前已经包含美国圣何塞和洛杉矶机房,以及这个月有新增的中国香港机房,根据大趋势云服务器算是比较技术流的趋势。传统的VPS主机架构方案在技术层面上稍微落后一些,当然也是可以用的。不清楚是商家出于对于传统VPS主机清理库存,还是多渠道的产品化营销,看到RAKSmart VPS主机提供美国、香港和日本机房的半价促销,当然也包括其他...

数脉科技:六月优惠促销,免备案香港物理服务器,E3-1230v2处理器16G内存,350元/月

数脉科技六月优惠促销发布了!数脉科技对香港自营机房的香港服务器进行超低价促销,可选择30M、50M、100Mbps的优质bgp网络。更大带宽可在选购时选择同样享受优惠,目前仅提供HKBGP、阿里云产品,香港CN2、产品优惠码续费有效,仅限新购,每个客户可使用于一个订单。新客户可以立减400元,或者选择对应的机器用相应的优惠码,有需要的朋友可以尝试一下。点击进入:数脉科技官方网站地址数脉科技是一家成...

速云:深圳独立服务器,新品上线,深港mpls免费体验,多重活动!

速云怎么样?速云是一家国人商家。速云商家主要提供广州移动、深圳移动、广州茂名联通、香港HKT等VDS和独立服务器。目前,速云推出深圳独服优惠活动,机房为深圳移动机房,购买深圳服务器可享受5折优惠,目前独立服务器还支持申请免费试用,需要提交工单开通免费体验试用,次月可享受永久8折优惠,也是需工单申请哦!点击进入:速云官方网站地址活动期限至 2021年7月22日速云云服务器优惠活动:活动1:新购首月可...

c语言求最大公约数为你推荐
meeyimevius是什么烟适合男人吸吗?常用软件开发工具单片机有哪些开发工具?bt4破解教程怎么破解无线网络密码:WPA/WPA2 PSK,最好有软件,教程,破了加分!!印象城市游戏论坛游聚游戏平台如何使用?云图好看吗云图这部电影好看吗云图好看吗电影《云图》看了两遍,还是没怎么看懂,那位大侠讲讲,要通俗易懂。nero教程如何使用NERO刻碟prepare的用法●请问大家关于prepare和prepare for的用法和区别~~~!!~~~~罗振宇2017跨年演讲“时间的朋友”跨年演讲办了多少场,分别是什么主题?罗振宇2017跨年演讲有时候拼命奔跑,只是为了留在原地是什么意思
高防服务器租用选锐一 中国万网域名 互联网域名管理办法 罗马假日广场 外国服务器 网络星期一 godaddy域名转出 debian源 网站挂马检测工具 双拼域名 建立邮箱 hostloc 腾讯实名认证中心 服务器是干什么的 息壤代理 hkt raid10 免费外链相册 阿里云官方网站 主机管理系统 更多