前言
對于初學編程的小伙伴們肯定經(jīng)常遇見此類問題，而且為之頭疼，今天我來給大家分享一下，最大公因數(shù)和最小公倍數(shù)的求法。讓我們開始吧！

1，最大公因數(shù)

首先提起最大公因數(shù)大家最先想到的就是輾轉(zhuǎn)相除法。
假如求a，b的最大公因數(shù)x。其中a>b。a可以表示為nb+t,那么t=a-nb,因為x是a和b的公因數(shù)，將等式兩邊同時除以x得，t/x=a/x-n*b/x,那么我肯可以知道t/x是個整數(shù)，所以x是a和a%b的公因數(shù)，那么我們可知那么x也是b和a%b的公因數(shù)。所以a和b的最大公約數(shù)和b和a%b的最大公約數(shù)是一樣的。那么我們就可以使用循環(huán)的方法求出最大公因數(shù)如下：

法1

#include<stdio.h>
int gcd(int a, int b)
{if (a > b)//判斷大小事大數(shù)除以小數(shù){int temp = a;a = b;b = temp;}while (a % b)//輾轉(zhuǎn)相除{int temp = a;a = b;b = temp%b;}
}
int main()
{int a, b;scanf("%d %d", &a, &b);int ans = gcd(a,b);printf("%d", ans);return 0;
}

那么這樣寫有點麻煩，我們可以直接使用遞歸的方法解決而且速度更快。

法2

#include<stdio.h>
int gcd(int a, int b)
{if (a == 0)//當a為0時，b為最大公因數(shù)return b;return gcd(b, a%b);
}
int main()
{int a, b;scanf("%d %d", &a, &b);int ans = gcd(a,b);printf("%d", ans);return 0;
}

那么有沒有更快的方法呢？當然有！我們都知道位運算的速度比除法運算快的多，那么我肯可以吧代碼改成這樣。

法3

#include<stdio.h>
int gcd(int a, int b)
{while (b ^= a ^= b ^= a %= b);//連等式是從右往左計算的，我們要知道a^a=0,a^0=a。那么連等式就可以等同于gcd（b,a%b）return a;
}
int main()
{int a, b;scanf("%d %d", &a, &b);int ans = gcd(a,b);printf("%d", ans);return 0;
}

這種算法是最快的

2，最小公倍數(shù)

正常求法求最小公倍數(shù)可能太過麻煩，但是我們要知道一個定理。假設x是a和b的最大公因數(shù)，y是a和b的最小公倍數(shù)，那么xy=ab。（如果不明白可以百度一下或者直接背下來當結論用）
所以我們就可以用上面的方法先求出x然后再用y=a*b/x求出y的值。

3，尾聲

本期的分享到這里結束，如果覺得博主講的不錯的話請給博主一個點贊一個收藏支持一下，我們下期再見！