兩個正整數最大公因數和最小公倍數的關系

最小公倍數除以最大公因數等于兩數之積
直接上圖：

因此我們只要會求兩個數的最大公因數，就可以很容易得到最小公倍數了，因此接下來我們主要求兩個數的最大公因數

更相減損術

原理：

對于兩個數91、168，設它們的最大公因數為m，則91，168都能被m整除（整除，即91%m==0），168-91=77，所以168可以寫成91+77，91可以被m整除，所以77也能被m整除，因此可以轉換為求91和77的最大公因數，再把91寫成77+14，說明14也能被m整除，轉換為求14和77的最大公因數，這樣一直下去，最后轉換為求14和7的最大公因數，再把14寫成7+7，也就是求7和7的最大公因數，那就是7咯，寫成算式就是：
168-91=77
91-77=14
77-14=63
63-14=49
49-14=35
35-14=21
21-14=7
14-7=7

代碼實作：

#include<stdio.h>
int main()
{
	int m, n;
	scanf("%d%d", &m, &n);
	int tmp = 0;//創建一個臨時變數，用作m，n交換時的中間變數
	while (n)
	{
		if (m < n)//如果m<n，交換兩個數的值
		{
			tmp = m;
			m = n;
			n = tmp;
		}
		n = m - n;
		m = m - n;
	}
	printf("%d", m);
}

結合著圖片看，就會發現先令n=m-n，再令m=m-n，就相當于把m-n的值賦給n，把原來n的值賦給m，也就和我們上面的算式對應起來了

輾轉相除法

原理：

輾轉相除法原理與更相減損術原理相似，給定兩個數168和91，168%91=77，就相當于168減去了一倍的91，91%77=14，就相當于91減去了一倍的77，77%14=7，相當于減去了5倍的14，相當于把五步和為一步！14%7=0，就說明最終結果就是7，結合上面更相減損數的轉換思路理解！

代碼實作：

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

這種方法與上面的方法原理相似，理解了上面的這個就不算難理解，而且這個演算法會節約一些時間，但是為什么這里不需要判斷m<n的特殊情況？因為當m<n時，tmp=m%n就相當于tmp=m,而再加上m=n，n=tmp，就相當于交換了m，n的值

窮舉法

原理：

對于兩個數m，n的最大公因數，一定小于等于m，n中較小的那一個，我們只需從m，n中較小的數開始回圈，找到第一個能整除m和n的那個數，即為最大公因數

代碼實作：

#include<stdio.h>
int main()
{
	int m, n;
	scanf("%d%d", &m, &n);
	int min = m > n ? m : n;//復習一下三目運算子
	int i = 0;
	for ( i = min; i >= 1; i--)
	{
		if (m % i == 0 && n % i == 0)
		{
			break;//一旦找到公因數就跳出回圈，即為最大公因數
		}
	}
	printf("%d", i);
}

Stein演算法

原理：

大事化小
首先引進一個符號：gcd是greatest common divisor（最大公約數）的縮寫，gcd( x,y ) 表示x和y的最大公約數，根據x，y的奇偶性我們可以進行轉換，
下面三種情況中x，y均為奇數

兩數都為偶數

則gcd( 2x , 2y )=gcd( x , y )*2
這個很容易明白

兩數一奇一偶

y為奇數，所以y的所有因數都是奇數，所以二者的公因數也只能是奇數，所以gcd( 2x, y )=gcd( x , y )

兩數都為奇數

這種情況乍一看沒什么可以化小的方法，但是兩個奇數的和、差都為偶數，這又引起我們的遐想！假設x>y

所以我們得到gcd( x,y )=gcd( (x+y)/2 ,(x-y)/2 )

那么接下來我們就可以把一個gcd( x , y )根據不同的情況化小，以求得答案

代碼實作：

x&1表示x與1進行位運算，如果x&1=1，則x為奇數（建議復習一下&運算）

int Stein(int x,int y)
{
    int m= 0,tmp=0;
    if(x<y)
    {
        tmp=y;
        y=x;
        x=tmp;
    }
    while(x!=y)
    {
        if(x&1)
        {
            if(y&1)//x,y同為奇數時
            {
                y = (x-y)>>1;//右移一位，即y=(x-y)/2
                x -= y;//即x=x-y
            }
            else//x為奇數，y為偶數時,這里x本就大于y，y/2后也必定大于y
            {
                y>>=1;//即y=y/2
            }
        }
        else
        {
            if(y&1)//x為偶數，y為奇數
            {
                x>>=1;
                if(x<y) //雖然x>y，但x/2后有可能小于y，再判斷一次
                {
                    tmp=y;
                    y=x;
                    x=tmp;
                }
            }
            else//x,y都為偶數
            {
                x>>=1;
                y>>=1;
                m++;
            }
        }
    }
    return x<<m;//因為x，y同除以2后，最大公因數變為原來的一半，所以回傳最大公因數時應該乘回來，而其它情況下x，y變化，最大公因數不變
}
int main()
{
    int x,y;
    scanf("%d%d",&x,&y);
    int gcd= Stein(x,y);//接收最大公因數
    printf("%d\n",gcd);
    return 0;
}

比如說我們代入168和91：

這其實和我們的遞回思想有些相似，實際上這種演算法也有遞回寫法，你可以試試哦！