撰寫原因
由于在刷題過程中總是會遇到一些比較基礎的數學知識，但是由于記憶模糊是以總是會想的很吃力，是以嘗試寫下這篇文章來記錄自己容易忘記的一些知識，希望自己能夠不斷更新這篇文章，使之較為全面。
公約數（common factor）
公約數，亦稱“公因數”。它是一個能被若幹個整數同時均整除的整數。如果一個整數同時是幾個整數的約數，稱這個整數為它們的“公約數”；公約數中最大的稱為最大公約數。對任意的若幹個正整數，1總是它們的公因數。公約數與公倍數相反。
擴充知識點：
求解最大公約數常用歐幾裡得算法（即輾轉相除法），一般用 gcd(a, b) 來表示 a 和 b 的最大公約數。
歐幾裡得算法基于下面這個定理：
設 a 、b 均為正整數，則 gcd(a, b) = gcd(b, a % b)。
用中文解釋就是指兩個數的最大公約數等于較小數與兩個數相除所得餘數的最大公約數。
相關代碼：
int gcd(int a, int b)
{
if(b == 0) return a;
else return gcd(b, a % b);
}
//更簡潔的寫法是：
int gcd(int a, int b)
{
return !b ? a : gcd(b, a % b);
}
希望能夠将之記牢。
公倍數（common multiple）
公倍數(common multiple)是指在兩個或兩個以上的自然數中，如果它們有相同的倍數，這些倍數就是它們的公倍數。公倍數中最小的，就稱為這些整數的最小公倍數（lowest common multiple）。
擴充知識點：
一般用 lcm(a, b) 來表示 a 和 b 的最小公倍數。最小公倍數的求解在最大公約數的基礎上進行，當得到 a 和 b 的最大公約數 d 之後，可以馬上得到 a 和 b 最小公倍數是 a*b / d。
自我了解：
當想要求得 a，b 之間的最小公倍數時，我們通常的想法是，先将兩者一起化簡到最簡狀态，如 4 : 6，化為最簡：2 : 3；然後将兩者相乘之後再乘以之前為了化簡所共同除的數，就會得到還原之後的最小公倍數，仔細研究會發現，要想化簡到最簡狀态，直接同時除以最大公約數就行，則可以表示為 a / d b / d d = ab / d；即所得方程。
注意點：
由于 ab 在實際運算中有可能溢出，是以更加恰當的寫法是 a / d * b。
素數（prime number）
質數又稱素數。一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數。
應特别注意的是： 1既不是素數也不是合數。
擴充知識點：
- 如何判定給定的正整數 n 是否是質數；
- 如何在較短的時間内得到 1 ~ n 的素數表。
素數的判斷
根據定義，一個整數要被判斷是素數，需要判斷 n 是否能被 2，3，…… n - 1 中的一個整除，若能，則不是質數，不能則是素數。但是這種方法複雜度較高為O(n)。容易推導隻需判斷 2，3，…… sqrt(n) 中任一個能否被整除（這裡的根号 n 向下取整），若能，則為非素數，至于為什麼是根号 n 向下取整，這裡不多贅述。
素數表的擷取
若從1開始周遊到 n - 1來擷取素數表，在資料較少的時候還可以使用，但是資料一旦超過105時，就将力不從心。
下面介紹一種最簡單且容易了解的一種更高效的算法，叫做 “埃氏篩法”， Eratosthenes篩法，複雜度為O(nloglogn)。更優的歐拉篩法可以達到O(n)，此處不予贅述。
素數篩法關鍵在于 “篩”。算法從小到大枚舉所有數，對每一個素數，篩去它所有倍數，剩下的就全是素數了。 如何了解呢？可以自己嘗試手算一下 1~15中的素數，先确定 2 是素數，然後删除2的所有倍數，然後找到下一個沒删除的素數如此循環，直到到最後一個數字。其實很容易了解，如果可以由素數的倍數所表示，那麼一定不是素數，而沒有被之前所留下的素數翻倍所删除的數字則一定是隻能被1和本身整除，是以也是素數。
代碼如下(求解100以内的素數表的程式)：
#include<cstdio>
const int maxn = 101;
int prime[maxn], pnum = 0;
bool p[maxn] = {0};
void find_prime()
{
for(int i = 2; i < maxn; i++)
{
if(p[i] == false)
{
prime[pnum++] = i;
for(int j = i + i; j < maxn; j += i)
{
p[j] = true;
}
}
}
}
int main()
{
find_prime(); //這個一定不要忘記，預處理
for(int i = 0; i < pnum; i++)
{
printf("%d", prime[i]);
if(i != pnum - 1)printf(" ");
}
return 0;
}
優化
這裡有個一個小優化，j 從 i * i 而不是從 i + i開始，因為 i*(2~ i-1)在 2~i-1時都已經被篩去，是以從i * i開始。
代碼如下
void find_prime()
{
for(int i = 2; i < maxn; i++)
{
if(p[i] == false)
{
prime[pnum++] = i;
int j = i * i;
while(j < maxn) //注意保證j不會超出maxn的範圍，否則就會段錯誤
{
p[j] = true;
j += i
}
}
}
}