辗转相除法c语言
Ⅰ c语言辗转相除法
例如用辗转相除法求a b 最大公约数（a b谁大谁小无所谓）：
int GCD( int a , int b )
{
int n=a%b;
whie(n != 0) //即： while(n)
{
a = b;
b = n;
n = a % b;
}
return b; //注意这里返回的是b 不是n
}
Ⅱ 什么是c语言里面的辗转相除法
用辗转相除法（即欧几里得算法）求两个正整数的最大公约数。
解析：
设两个数m,n，假设m>=n，用m除以n，求得余数q。若q为0，则m为最大公约数；若q不等于0，则进行如下迭代：
m=n,n=q,即原除数变为新的被除数，原余数变为新的除数重复算法，直到余数为0为止。余数为0时的除数n，即为原始m、n的最大公约数。
迭代初值：m，n的原始值；
迭代过程：q=m%n;
m=n;
n=q;
迭代条件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因为：(q==2)!=0，重复算法：
q=m%n(6%2==0)
m=n(m==2)余数为0时的除数n为最大公约数，n值赋给了m，所以输出m的值
n=q(n==0)
因为：q==0 所以最大公约数为m的值
源程序：
#include<stdio.h>
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",&a,&b);
m=a;
n=b;
if(n>m)
{
int z;
z=m;m=n;n=z;//执行算法前保证m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf("The greatest common divisor of");
printf("%d,%d is %d\n",a,b,m);
}
希望对你有所帮助!
Ⅲ c语言求最大公约数辗转相除法
int main(void)
{
printf("这是两个整数求最大公约数的算式，请输入两个不相等的正整数，并按回车键确认：\n"); //操作提示
intm,n,r,i; //定义四个整形变量
scanf("%d %d",&m,&n); //输入m和n的值
if(m<n) {i=m;m=n;n=i;} //如果m<n，借用变量i进行m和n的数值互换
while(m%n!=0) //m取模n 赋值给r
{r=a%b;m=n;n=r;} //余数不等于0，则n的值给m，r的值给n，再次进入循环
printf("它们的最大公约数是%d\n",n);
system("PAUSE");
return 0;
}
Ⅳ 辗转相除法求最大公约数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语言代码
辗转相除法用来求两个数的最大公约数，代码如下：
#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 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>
intgcd(intx,inty)
{
inti;
intmax,min;
(x>y)?(max=x,min=y):(max=y,min=x);
if(i=max%min!=0)
do{
i=min;
min=max%min;
max=i;
}while(min!=0);
returnmax;
}
intmain()
{
inta,b;
scanf("%d%d",&a,&b);
printf("%d ",gcd(a,b));
return0;
}
再给你一个精简版，二者实质是一样的
#include<stdio.h>
intgcd(intx,inty)
{
if(y==0)returnx;
returngcd(y,x%y);
}
intmain()
{
inta,b;
scanf("%d%d",&a,&b);
printf("%d ",gcd(a,b));
return0;
}
Ⅷ 辗转相除法c语言
这是求最大公约数的，没有问题啊，是不是你输入出错了，示例运行结果如下：
12,8
gcd=4
16,36
gcd=4
中间的逗号不能少的哦，否则就会出错了，因为scanf("%d,%d",&a,&b);的%d,%d中间是有都逗号的呀。