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

编辑:谯胜平      分类:程序与算法      标签:最大公约数,最小公倍数      发布时间:2019-05-11      浏览次数:885

一、分析

   设a,b均为正整数。

  • 最大公约数

    gcd(a, b)表示求最大公约数。使用欧几里得算法(即辗转相除法),其基本公式如下:

    递归式:gcd(a, b) = gcd(b, a % b); 

    递归边界:gcd(a, 0) = a;

  • 最小公倍数

    lcm(a, b)表示求最小公倍数。通过最大公约数可以很快求出最小公倍数,其公式如下:

    lcm(a, b) = a * b / gcd(a, b) = a / gcd(a, b) * b(防止a*b溢出);

二、代码

  • 最大公约数:

#include<stdio.h>
#include<algorithm>

//最大公约数 
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int main()
{
	int a, b;
	while(scanf("%d %d", &a, &b)!= EOF){
		printf("%d\n", gcd(a, b));
	}
	return 0;
}
  • 最小公倍数:

#include<stdio.h>
#include<algorithm>

//最大公约数 
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}

//最小公倍数 
int lcm(int a, int b){
	return a / gcd(a, b) * b;
} 

int main()
{
	int a, b;
	while(scanf("%d %d", &a, &b)!= EOF){
		printf("%d\n", lcm(a, b));
	}
	return 0;
}


看不清?换一个