欧几里德求最大公约数/最小公倍数-白红宇

欧几里德求最大公约数/最小公倍数

阅读量：4216 次

发布时间：2019-05-26

本文共 1707 字，大约阅读时间需要 5 分钟。

两个数的最大公约数（递归/递推）

1、辗转相除法的正确性gcd(a,b)=gcd(b,a mod (b))的证明：

第一步：令c为a和b的最大公约数，数学符号表示为c=gcd(a,b).因为任何两个实数的最大公约数c一定是存在的，也就是说必然存在两个数k1,k2使得a=k1*c, b=k2*c

第二步：a mod (b)等价于存在整数r,k3使得余数r=a – k3*b.

即r = a – k3*b

= k1*c – k3*k2*c

= (k1 – k3*k2)*c

显然，a和b的余数r是最大公因数c的倍数，反复执行此法可以把r不断减小为1倍此时a%b == 0

可得此时的b即为最大公约数

1、两个数的最大公约数

#include
   
    using namespace std;	int reGcd(int a, int b){	if(b == 0){		return a;	}	return reGcd(b, a%b);}	int gcd(int a, int b)	{				while(b != 0){			t = a%b;			a = b;			b = t;		}		return a;	}int main()	{		int a, b;		cin >> a >> b;		int t, m;		if(a  < b ){			t = a;			a = b;			b = t;		}		t = gcd(a, b);		m = reGcd(a, b);		cout << t <<" "<< m;		return 0;	}

2、两个数的最小公倍数

int lcm(int a, int b){ 	int t = gcd(a, b); 	return a*b/t;}

二、多个数的最大公约数、最小公倍数

、最大公约数

求最小值

int getMin(int a, int b, int c){	int t;	if( a > b) {		t = a; a = b; b = t;	}	if( a > c){		t = a; a = c; c = t;	}	if(b > c){		t = b; b = c; c = t;	}	return a;}

从最小值开始找最大公约数

int mulGcd(int a, int b, int c){	int m = getMin(a,b,c);	for(int i = m; ; i--){		if(a%i == 0 && b%i == 0 && c%i == 0){			return i;		}	}}

2、最小公倍数（可以从最大的数开始提高效率)

注意：多个数的最小公倍数不可以用a*b*c/gcd(a,b,c)的方式求

int mulLcm(int a, int b, int c){	for(int i = a; ;++i){		if(i%a == 0 && i%b == 0 && i%c == 0){			return i;		}	}}

多个数的最大公约数：

就是对所有的数依次迭代求公约数

例如a,b,c 的公约数 g = gcd(a,b) g = (g,c);

原理：设d = gcd(a,b)则 d|a, d|b 公约数必然小于等于d 现在求得t = gcd(d,c) 则t|d且t|c 则t|a且t|a,t|b,t|a所以求得的t是abc的最大公约数

#include
   
    int gcd(int a, int b)	{		return b ? gcd(b,a%b) : a;	}int a[100];int main()	{		int n;		scanf("%d",&n);		for(int i = 0; i < n; ++i){			scanf("%d",&a[i]);		}		int g = a[0];		for(int i = 1; i < n; ++i){			g = gcd(g,a[i]);//核心 		}		printf("gcd = %d",g);		return 0;	}

转载地址：http://wmimi.baihongyu.com/

你可能感兴趣的文章

普陀区委副书记顾军、区政府副区长魏静带队调研上海控安