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

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