欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

GCD最大公约数

程序员文章站 2024-03-20 12:03:40
...

-GCD

已知两个正整数a,b求最大公约数。

  • (a,b)可以写成a=b* q1+r1的形式(q1,r1都是实数)(a,b)的GCD即为(b,r1)的GCD
    所以b=r1* q2+r2;
    r1=r2* q3+r3;
    ……
    rn=rn+1* qn+2;
    所以最大公约数为qn+2。

证明:(a,b)的GCD即为(b,r)的GCD (a=b * n+r)
设v为a,b的公约数
a=tv,b=qv
r=a-bn=tv-qnv=v(t-qn),所以v是r的因子;
设u为b,r的公约数
b=xu,r=yu
a=bn+r=xun+yu=u(xn+y),所以u是a的因子。
代码如下(两种方法):

  • 循环
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	while(b)
	{
		int mid=a;
		a=b;
		b=mid%b;
	}
	printf("%d\n",a);
	return 0;
}
  • 递归
int gcd(int a,int b)
{
	if(b==0)
		return a;
	gcd(b,a%b);
}

如有错误,欢迎指正