輾轉相除法:
這算法可不一般，是世界上已知最早的算法，歐幾裡得在公元前300多年提出的。
就是這位大佬
它的具體做法是：用較大數除以較小數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。
可能聽著很懵對吧，我們用具體數據來試驗一下
其中"a mod b"是指取 a ÷ b 的餘數。
例如，123456 和 7890 的最大公因數是 6，這可由下列步驟看出:
a
b
a mod b
123456
7890
5106
7890
5106
2784
5106
2784
2322
2784
2322
462
2322
462
12
462
12
6
12
6
0
如果你還是很懵，沒關係，我們再看下圖
這個過程本質是把一個複雜的問題轉化為更簡單的問題，所以我們可以用遞歸。貼出c語言的代碼：
（ 看懵了吧）
（我錯了，不敢得瑟了正常人能看懂的代碼獻上）
更相減損法:
更相減損術是出自《九章算術》的一種求最大公因數的算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。
原文是這樣的：
可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。
什麼意思呢？具體步驟如下：
第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡（這一步可以不做，只不過約簡後能使計算簡便）； 若不是則執行第二步。
第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，並以大 數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2的積與第二步中等數的乘積就是所求的最大公約數。
例：求24和6的最大公因數
一.24和6都能用2約簡，得12和3
二.12-3=9
三.9-3=6
四.6-3=3 （出現了）減數和差相等
五.於是2*3=6就是12與6的最大公約數
至於為什麼這樣算，其實本質上與輾轉相除法並沒有什麼區別，這裡就不再贅述了，下面直接給出C語言的原始碼：
最後，非常感謝您的支持，如果您有什麼疑問，非常歡迎您私信曉影或者在評論區留下您寶貴的意見或建議
附：原始碼（偷懶專用，可直接複製粘貼）
輾轉相除法：
#include<stdio.h>
int main()
{
int a,b;
scanf("%d%d",&a,&b);
if(a<=b)//讓a>b
{
a=a+b;
b=a-b;
a=a-b;
}
while(a%b!=0)
{
b=a%b;
a=b;
}
printf("最大公因數是%d",b);
return 0;
}
更相減損術：
#include <stdio.h>
int main()
{
int a,b;
scanf("%d%d",&a,&b);
while(a != b)
{
if(b<a)a=a-b;
else b=b-a;
}
printf("最大公因數為%d",a);
return 0;
}