C语言实现辗转相除法(两种方法)
程序员文章站
2024-03-12 16:12:20
...
辗转相除法:
又名“欧几里德算法”
图片来自搜狗搜索。
第一种方式:
根据定义就可以写出一种比较简单的实现方法:、
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
int a,b,c;
scanf("%d %d",&a,&b);
c=a%b;
while(c!=0)
{
a=b;
b=c;
c=a%b;
}
printf("%d",b);//将除数输出
return 0;
}
第二种方式:
熟练掌握辗转相除法之后,可以用递归的形式来实现:
#include <stdio.h>
#include <stdlib.h>
//递归函数
int gcd(int a,int b){
if(b==0) return a;//返回a,即返回上一步的b
return gcd(b,a%b);
}
int main(int argc, char *argv[]) {
int a,b;
scanf("%d %d",&a,&b);
printf("%d",gcd(a,b));
return 0;
}
上一篇: Python文件和输入输出