求最大公约数和最小公倍数的算法

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

在刷题的过程中,经常会遇到很多关于最小公倍数和最大公约数的问题。

以下是用C语言写的求最大公约数和最小公倍数的算法。

最大公约数。

求最大公约数有三种算法。

1、辗转相除法。

      辗转相除法又称为欧几里德算法。这个方法大家已经都已经在数学上学过了。具体的步骤就是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。最后的除数就是这两个数的最大公约数。举个例子就是:比如两个数字,x=453,y=36;

453%36=21;

36%21=15;

21%15=6;

15%6=3;

6%3=0;

%是取余符号,大家应该都知道吧。所以用这个算法可以求出453和36的最大公约数是3;

用C语言实现这个算法就是。

#include <stdio.h> int main(){	int a,b,c;	scanf("%d%d",&a,&b);	while(b)	{		c=a%b;		a=b;		b=c;	}	printf("%d\n",a);	return 0;}

或者是

#include <stdio.h> int gcd(int a,int b){	return b?gcd(b,a%b):a;}int main(){	int a,b,c;	while(scanf("%d%d",&a,&b)!=EOF)	{		c=gcd(a,b);		printf("%d\n",c);	}	return 0;}

2、更相减损法

       更相减损法是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。又名“更相减损术”,辗转相减法,等值算法,尼考曼彻斯法

比如说还是453和36;

453-36=417;

417-36=381;

381-363=345

.。。。。。。

9-6=3

6-3=3

3-3=0

然后3就是这两个数的最大公约数。

#include <stdio.h> int main(){	int a,b;	while(scanf("%d%d",&a,&b)!=EOF)	{		while(a!=b)		{			if(a>b)				a=a-b;			else				b=b-a;					}		printf("%d\n",a);	}	return 0;}

3、穷举法

从1开始循环,一直循环到两个数中小的那个数。

#include <stdio.h> int main(){	int a,b,c;	while(scanf("%d%d",&a,&b)!=EOF)	{		int max=1;       //记录最大公约数 		c=a>b?b:a;      //c等于a和b中小的数 		for(int i=1;i<=c;i++)		{			if(a%i==0&&b%i==0)			{				if(i>max)					max=i;			}		}		printf("%d\n",max);	}	return 0;}

最小公倍数

求最小公倍数相对来说就比较简单了。只需要先求出最大公约数。用两个数的乘积除以最大公约数即可。

例如x和y的最小公倍数为x*y/gcd(x,y)。(gcd(x,y)表示为两个数的最大公约数)

#include <stdio.h> int gcd(int a,int b){	return b?gcd(b,a%b):a;}int main(){	int a,b,c;	while(scanf("%d%d",&a,&b)!=EOF)	{		c=a*b/gcd(a,b);		printf("%d\n",c);	}	return 0;}

点这里可以跳转到人工智能网站