質數與合數

定義

質數又稱素數，有無限個。質數定義為在大于1的自然數中，除了1和它本身以外不再有其他因數。

合數指自然數中除了能被1和本身整除外，還能被其他數（0除外）整除的數。與之相對的是質數，而1既不屬于質數也不屬于合數。最小的合數是4。其中，完全數與相親數是以它為基礎的。

性質

若n為合數，則n至少有一個質因子，是以其中最小的質因子一定不大于\(\sqrt n\)

質數有無窮多個，不大于n的質數有\(\displaystyle \frac{n}{ln \ n}\)個

證明質數有無限多個（反證法）

證明：

我們不妨假設質數有有限個，共有n個

分别為\(p_1, p_2, p_3...p_n\)

我們令\(\displaystyle x = \prod_{i = 1}^n p_i \ \ + 1\)

我們可以看出\(x與p_1...p_n\)中的任何一個數都不整除，都餘1

而且\(x>p_1...p_n\) 中的任意一個數

\(\therefore x\)為質數。

\(\therefore\) 假設不成立，即質數有無窮多個

算數基本定理（唯一分解定理）

每個大于1的自然數均可寫為質數的積，而且這些素因子按大小排列之後，寫法僅有一種方式。 ---知乎

也就是\(n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}\)

證明:（反證法）

為了真正地證明，分解質因數的方法是唯一的，我們将再次用到反證法。

假設存在某些數，它們有至少兩種分解方法。

那麼根據上文提到的“非空正整數集裡存在最小的元素”，一定有一個最小的數M，它能用至少兩種方法表示成質數的乘積：

\(M = P_1 * P_2 * … * P_r = Q_1 * Q_2 * … * Q_s\)

下面我們将看到，這種假設會推出一個多麼荒謬的結果來。

不妨設\(P_1 <= P_2 <= … <= P_r, Q_1 <= Q_2 <= … <= Q_s\)。

顯然，\(P_1\)是不等于\(Q_1\)的，不然兩邊同時約掉它，我們就得到一個更小的有兩種分解方法的數。

不妨設\(P_1 < Q_1\)，那麼我們用\(P_1\)替換掉等式最右邊中的\(Q_1\)，得到一個比\(M\)更小的數\(T = P_1 * Q_2 * Q_3 * … * Q_s\)。

令\(M’ = M – T\)，我們得到\(M’\)的兩種表達：

$M’ = (P_1 * P_2 * … * P_r) – (P_1 * Q_2 * … * Q_s) $

\(\ \ \ \ \ = P_1 * (P_2 * .. * P_r – Q_2 * … * Q_s) \ ①\)

$M’ = (Q_1 * Q_2 * … * Q_s) – (P_1 * Q_2 * … * Q_s) $

\(\ \ \ \ = (Q_1 – P_1) * Q_2 * … * Q_s \ ②\)

由于\(T\)比\(M\)小，是以\(M’\)是正整數。

從①式中我們立即看到，\(P_1\)是\(M’\)的一個質因子。

注意到\(M’\)比\(M\)小，是以它的質因數分解方式應該是唯一的，可知\(P_1\)也應該出現在表達式②中。

既然\(P_1\)比所有的\(Q\)都要小，是以它不可能恰好是(2)式中的某個\(Q\)，于是隻可能被包含在因子\((Q_1-P_1)\)裡。

但這就意味着，\(\frac {Q_1-P_1}{P_1}\)除得盡，也就是說\(\frac {Q_1}{P_1-1}\)是一個整數，

這樣\(\frac {Q_1}{P_1}\)也必須得是整數。我們立即看出，\(P_1\)必須也是\(Q_1\)的一個因子，這與\(Q_1\)是質數沖突了。

這說明，我們最初的假設是錯誤的。

例題 CF776 B

傳送門

顯然這是一個沙比題

我們可以質數塗一種顔色，合數塗一種顔色，也就是兩種

但是注意a可以等于b是以當a==b時答案是1