最大公约数辗转相除法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语言程序:用“辗转相除法”求两个正整数的最大公约数(程序填空)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a, b,r;
scanf("%d %d", &a, &b);
while (b != 0)//当其中一个数为0，另一个数就是两数的最大公约数
{
r = a%b;
a = b;
b = r;
}
printf("最大公约数%d ", a);
system("pause");
}
例子：
105252
252％105＝42；
105％42＝21；
42％21＝0；
即21为105与252的最大公约数
(2)最大公约数辗转相除法c语言扩展阅读：
while语句若一直满足条件，则会不断的重复下去。但有时，需要停止循环，则可以用下面的三种方式：
一、在while语句中设定条件语句，条件不满足，则循环自动停止。
如：只输出3的倍数的循环；可以设置范围为：0到20。
二、在循环结构中加入流程控制语句，可以使用户退出循环。
1、break流程控制：强制中断该运行区内的语句，跳出该运行区，继续运行区域外的语句。
2、continue流程控制：也是中断循环内的运行操作，并且从头开始运行。
‘叁’ c语言中，用辗转相除法计算两个数的最大公约数的具体方法是怎样的
#include <stdio.h>
int gcd(int a, int b) {
int r;
do {
r = a % b;
a = b;
b = r;
} while (r);
return a;
}
int main(void) {
int a, b;
printf("Input two integers: \n");
scanf("%d%d", &a, &b);
printf("The greatest common divisor is: %d\n", gcd(a, b));
return 0;
}
原理：
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数，则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤r<b）
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步
‘肆’ 辗转相除法c语言代码
辗转相除法用来求两个数的最大公约数，代码如下：
#include<stdio.h>
#include<stdlib.h>
intmain()
{
inta,b,r;
scanf("%d%d",&a,&b);
while(b!=0)//当其中一个数为0，另一个数就是两数的最大公约数
{
r=a%b;
a=b;
b=r;
}
printf("GreatestCommonDivisor:%d ",a);
system("pause");
}
运行结果：
‘伍’ 编程一个C语言程序,输入两个数,采用辗转相除法来计算最大公约数
可以参考下面的代码：
#include <stdio.h>
int main()
{
int m, n, r;
scanf ("%d%d", &m, &n);
if (m>n){r=m, m=n, n=r;}
r=n%m;
while (r!=0){
n = m;
m = r;
r = n%m;
}
printf ("%d ", m);
return 0;
}
(5)最大公约数辗转相除法c语言扩展阅读：
函数 scanf() 是从标准输入流stdin(标准输入设备，一般指向键盘)中读内容的通用子程序，可以说明的格式读入多个字符，并保存在对应地址的变量中。
函数的第一个参数是格式字符串，它指定了输入的格式，并按照格式说明符解析输入对应位置的信息并存储于可变参数列表中对应的指针所指位置。每一个指针要求非空，并且与字符串中的格式符一一顺次对应。
‘陆’ C语言求最大公约数
这个叫做辗转相除法，是中国古代标准的求最大公约数的方法。两个数正整数a〉b，如果a%b(a除b的余数)=0，b就是最大公约数;否则比较b与a÷b的余数c=a%b，两者相除，余数为0,c是最大公约数;否则继续比较c与b%c(余数)，……，反复交换进行，直到余数为0
‘柒’ c语言辗转相除法求最大公约数
可用递归来求。
推荐以下代码：
#include<stdio.h>
intgcd(inta,intb)//求最大公约数函数
{
if(a%b==0)returnb;
elsereturngcd(b,a%b);//辗转相除法
}
voidmain()
{
inta,b;
scanf("%d%d",&a,&b);
printf("%d ",gcd(a,b));
}
‘捌’ 辗转相除法求最大公约数c语言代码
辗转相除法是在在维基网络中的意思是：
在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（ {\displaystyle 252=21\times 12;105=21\times 5} {\displaystyle 252=21\times 12;105=21\times 5}）；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如 21 = 5 × 105 + (−2) × 252 。这个重要的结论叫做裴蜀定理。
在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分
简单的来说辗转相除法的原理就是：
先比较两个数使第一个数为最大数a，第二个数为最小数b
使最大数%最小数得到余数a%b=temp
后将余数赋值给最小数a=temp再去除最大数b即b%a
一直往复直到余数不为0
‘玖’ C语言 公约数辗转相除法
如果两个数有最大公约数A，那么这两个数，以及这两个数的差，还有大数除以小数的余数，必然都是A的倍数。
所以当最后两个数刚好能整除时，较小的数就是最大公约数。
建议你单步调试
深刻理解。。
下面是更加具体的：
对于两个数,我们要求是正整数,我们一般用辗转相除法两个数的最大公约数,下面我来仔细讲讲辗转相除法两个数的最大公约数的原理.
我们假设这两个数分别是X,Y,他们最大的公约数为M,则有X=a*M,Y=b*M(a,b是互质的数),很明显,我们的目的就是要把M的系数降到一,为此我们进行X%Y运算,实际上X%Y=(a%b)*M,由于a%b小于b,所以M的系数将会减小,接着我们进行Y%((a%b)*M)=(b%(a%b))*M,同理,则有b%(a%b)<(a%b),可见随着这样取余的操作M的系数会越来越小,前面已经说过,我们的目标是使M的系数降到一,而一是任何整数的约数,换句话说任何整数除一取余后为0,所以当取余之后的数为0,也就意味着M之前的系数为1,此时的被除数就是最大公约数,
举个例子
24
与
15
24=8*3
15=5*3
24%15=(8%5)*3=3*3=9;
15%9=(5%3)*3=2*3=6
9%6=(3%2)*3=3
6%3=(2%1)*3=0
-------------------------------被除数3就是24与5的最大公约数
两个正整数的最大公约数求出来之后他们的最小公倍数也就知道了,最小公倍数=两个数相乘除以他们的最大公约数,
原理很简单,不加详述.
在
C++中,求最大公约数的代码如下
int
gys(int
a,int
b)
//a必须要大于b
{
int
r=a%b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
return
b;
}
求最小公倍数的代码很简单,如下
int
gbs(int
a,int
b)//a必须要大于b
{
return
a*b/gys(a,b);
}
好了,有错误之处还请指正
‘拾’ c语言四种方法求最大公约数
c语言四种方法求最大公约数的方法依次是。第1种穷举法。第2种辗转相减法。第3种辗转相除法（包括递归的和非递归的）。