Horace Chan

最大公约数与最小公倍数

定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d a, d b，而r = a - kb，因此d r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d b , d r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

最大公约数 GCD

辗转相除法（欧几里得算法）

定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d | a, d | b，而r = a - kb，因此d | r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d | r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

这是一种函数的嵌套调用的方法

其算法的过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给b；
5、返回第二步；

一般写法

#include<iostream>
using namespace std;
int divisor(int a,int b)           //自定义函数求最大公约数
{
	int temp;                   //整形零时变量
	if(a<b)                     //a<b 则交换 
	{
		temp=a;a=b;b=temp;
	}
	while(b!=0)
	{
		temp=a%b;              //a中大数除以b中小数循环取余，直到b及余数为0
		a=b;
		b=temp;
	}
	return a;                  //返回最大公约数到调用函数处
}
int multipile(int a,int b)         //自定义函数求最小公倍数
{
	int divisor(int a,int b);       //自定义函数返回值类型
	int temp;
	temp=divisor(a,b);          //再次调用自定义函数，求出最大公约数
	return(a*b/temp);           //返回最小公倍数到主调函数处进行输出
}
int main()
{
	int m,n,t1,t2;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)
	{	
		printf("请重新输入正确整数：");
		cin.clear();                //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=divisor(m,n);
	t2=multipile(m,n);
	printf("最大公因数为：%d\n",t1);
	printf("最小公倍数为：%d\n",t2);
	return 0;
}

递归写法

int gcd(int a,int b){
    if(b <mark> 0)
        return a;
    return gcd(b,a%b);
}

int main()
{
    int a = 12,b = 18;
    int res = gcd(a,b);
    printf("The GCD is %d",res);
    return 0;
}

图解 欧几里得算法流程图

更相减损术

更相减损法：更相减损术， 出自于中国古代的《九章算术》，也是一种求最大公约数的算法。
  ①先判断两个数的大小，如果两数相等，则这个数本身就 是就是它的最大公约数。
  ②如果不相等，则用大数减去小数，然后用这个较小数与它们相减的结果相比较，如果相等，则这个差就是它们的最大公约数，而如果不相等，则继续执行②操作。

int gcd(int a,int b){
    while (true)//用大数减去小数并将结果保存起来
    {
        if (a > b)
        {
            a -= b;
        }
        else if(a < b)
        {
            b -= a;
        }
        else//如果两个数相等时，则这个数就是最大公约数
        {
            return a;
        }
    }
}

int main()
{
    int a = 12,b = 18;
    int res = gcd(a,b);
    cout << a << "和"<< b << "的最大公约数是" << res<<endl;
    return 0;
}

图解 更相减损法流程图

Stein 算法

[! SUMMARY] 结合辗转相除法和更相减损法的优势以及移位运算

众所周知，移位运算的性能非常快。对于给定的正整数a和b，不难得到如下的结论。其中gcb(a,b)的意思是求a,b的最大公约数的函数

  1. 当a和b均为偶数，gcb(a,b) = 2_gcb(a/2, b/2) = 2_gcb(a>>1, b>>1)
  2. 当a为偶数，b为奇数，gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
  3. 当a为奇数，b为偶数，gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)
  4. 当a和b均为奇数，利用更相减损术运算一次，gcb(a,b) = gcb(b, a-b)， 此时a-b的结果必然是偶数，又可以继续进行移位运算。
int gcd(int a,int b){
    if(a </mark> 0) return b;
    if(b <mark> 0) return a;
    if(a % 2 </mark> 0 && b % 2 <mark> 0) return 2 * gcd(a >> 1, b >> 1);
    else if(a % 2 </mark> 0)  return gcd(a >> 1, b);
    else if(b % 2 <mark> 0) return gcd(a, b >> 1);
    else return gcd(abs(a - b), min(a, b));
}

int main()
{
    int a = 12,b = 18;
    int res = gcd(a,b);
    cout << a << "和"<< b << "的最大公约数是" << res<<endl;
    return 0;
}

函数非递归调用

#include<iostream>
using namespace std;
int Stein( unsigned int x, unsigned int y )         //函数非递归调用
{     
    int factor = 0;                           //返回最大公约数x和y 
    int temp;
    if ( x < y )
	{ 
		temp = x;
		x = y;
		y = temp;
	}
	if ( 0 </mark> y )
	{
		return 0;
	}
	while ( x != y )
	{                                      //当x时偶数时 
		if ( x & 0x1 )
		{
			if ( y & 0x1 )
			{                               //当x和y都是偶数时 	
				y = ( x - y ) >> 1;
				x -= y;
			}
			else
			{                                //当x是偶数，y是奇数 	
				y >>= 1;
			}
		}
		else
		{                                    //当x是奇数 
			if ( y & 0x1 )
			{
				x >>= 1;
				if ( x < y )
				{
					temp = x;
					x = y;
					y = temp;
				}
			}
			else
			{                                //当x和y都是奇数 
				x >>= 1;
				y >>= 1;
				++factor;
			}
	}
	}
	return ( x << factor );
}
int main()
{
	int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)        //判断输入两数字是否小于零或为小数
	{	
		printf("请重新输入正确整数：");
		cin.clear();                            //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=Stein(m,n);
	printf("最大公因数为：%d\n",t1);
	return 0;	
}

函数递归调用

#include<iostream>
using namespace std;
int gcd(int u,int v)
{
    if (u <mark> 0) return v;
    if (v </mark> 0) return u;
                                       // 寻找两个数的最大公约数
    if (~u & 1)                        // u是偶数
    {
        if (v & 1)                     // v是奇数
            return gcd(u >> 1, v);
        else                            // u和v都是偶数
            return gcd(u >> 1, v >> 1) << 1;
    }
     if (~v & 1)                         // u是奇数, v是偶数
        return gcd(u, v >> 1);
                                         // 减少较大的变量
    if (u > v)
        return gcd((u - v) >> 1, v);
     return gcd((v - u) >> 1, u);
}
int main()
{
	int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)     //判断输入两数字是否小于零或为小数
	{	
		printf("请重新输入正确整数：");
		cin.clear();                              //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=gcd(m,n);
	printf("最大公因数为：%d\n",t1);
	return 0;
}
#include<iostream>
using namespace std;
int gcd(int u,int v)
{
    if (u <mark> 0) return v;
    if (v </mark> 0) return u;
                                       // 寻找两个数的最大公约数
    if (~u & 1)                        // u是偶数
    {
        if (v & 1)                     // v是奇数
            return gcd(u >> 1, v);
        else                            // u和v都是偶数
            return gcd(u >> 1, v >> 1) << 1;
    }
     if (~v & 1)                         // u是奇数, v是偶数
        return gcd(u, v >> 1);
                                         // 减少较大的变量
    if (u > v)
        return gcd((u - v) >> 1, v);
     return gcd((v - u) >> 1, u);
}
int main()
{
	int m,n,t1;
	printf("请输入两个整形数字：");
	scanf("%d%d",&m,&n);
	if(m<0||n<0||(m-(int)m)>0||(n-(int)n)>0)     //判断输入两数字是否小于零或为小数
	{	
		printf("请重新输入正确整数：");
		cin.clear();                              //清除错误标记，重新打开输入流
		cin.sync ();
		scanf("%d%d",&m,&n);
	}
	t1=gcd(m,n);
	printf("最大公因数为：%d\n",t1);
	return 0;
}

图解 Stein 算法 流程图

最小公倍数 LCM

公式法

由于对于任意两个整数，他们的最小公倍数与最大公约数的乘积等于这两个数的乘积

int multipile(int a,int b)         //自定义函数求最小公倍数
{
	int divisor(int a,int b);       //自定义函数返回值类型
	int temp;
	temp=divisor(a,b);          //再次调用自定义函数，求出最大公约数
	return(a*b/temp);           //返回最小公倍数到主调函数处进行输出
}

分解质因数法

先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。