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

Friendhosting 黑色星期五 VDS/VPS可享四五折优惠促销

Friendhosting商家在前面的篇幅中也又陆续介绍到,是一家保加利亚主机商,主要提供销售VPS和独立服务器出租业务,数据中心分布在:荷兰、保加利亚、立陶宛、捷克、乌克兰和美国洛杉矶等。这不近期黑色星期五活动,商家也有推出了黑五优惠,VPS全场一次性45折,虚拟主机4折,全球多机房可选,老用户续费可获9折加送1个月使用时长,VDS折后最低仅€14.53/年,有需要的可以看看。Friendhos...

HostSailor:罗马尼亚机房,内容宽松;罗马尼亚VPS七折优惠,罗马尼亚服务器95折

hostsailor怎么样?hostsailor成立多年,是一家罗马尼亚主机商家,机房就设在罗马尼亚,具说商家对内容管理的还是比较宽松的,商家提供虚拟主机、VPS及独立服务器,今天收到商家推送的八月优惠,针对所有的产品都有相应的优惠,商家的VPS产品分为KVM和OpenVZ两种架构,OVZ的比较便宜,有这方面需要的朋友可以看看。点击进入:hostsailor商家官方网站HostSailor优惠活动...

DiyVM:50元/月起-双核,2G内存,50G硬盘,香港/日本/洛杉矶机房

DiyVM是一家比较低调的国人主机商,成立于2009年,提供VPS主机和独立服务器租用等产品,其中VPS基于XEN(HVM)架构,数据中心包括香港沙田、美国洛杉矶和日本大阪等,CN2或者直连线路,支持异地备份与自定义镜像,可提供内网IP。本月商家最高提供5折优惠码,优惠后香港沙田CN2线路VPS最低2GB内存套餐每月仅50元起。香港(CN2)VPSCPU:2cores内存:2GB硬盘:50GB/R...

c语言求最大公约数为你推荐
office软件包office2007在哪能下载完整的软件包win7无线局域网win7怎么建立无线局域网联机玩游戏?magento2MRP与MRP2的区别呼叫中心搭建呼叫中心有几种建设方式啊?那种最省钱?物联卡官网物联卡9.9元100g流量卡是真的吗创业好项目论坛大学生创业有什么好的项目啊?催收软件哪个好我也欠了好多都是七天贷款高利息的,没钱还,今天开始催收,还爆了我的通讯录,弄得我想死的心都有了!智能公共广播系统有谁知道公共广播系统都包括那些设备金山铁路最新时刻表金山北至上虞北高铁时间表魔兽世界密保卡魔兽世界的密保卡怎么申请
fc2最新域名 哈尔滨服务器租用 如何注销域名备案 便宜服务器 fastdomain 512m内存 华为4核 paypal注册教程 空间首页登陆 什么是web服务器 石家庄服务器托管 全能空间 免费蓝钻 美国迈阿密 空间申请 卡巴斯基试用版下载 杭州电信宽带 小夜博客 asp介绍 卡巴斯基免费版 更多