<我有你沒有，你有我沒有，之到底誰有誰沒有?來不及打完的(一)>
腦袋嗎? 圖/Mgmoscatello @ Wikimedia Commons 腦袋嗎? 互質 啦! 什麼是互質? 如果兩個正整數(這兒僅簡單討論正整數)的最大公因數是1，則這兩個數互質。也就是兩個數沒有(除了1以外的)共同的因數，換句話說，正整數A的因數不會出現在B裏頭，反之亦然。 從小到大一定有寫過一種題目，通常長這樣，請問在...之內與...互質的數有幾個? 確切來說，舉個例子，請問在25內與30互質有幾個? 於是乎開始列出1到25，然後一個一個檢查，反正也才25個嘛~ 1跟30，2跟30，3跟30，4跟30，5跟30，6跟30，7跟30， 哦哦 ，8跟30，blablabla... 在後來我們發展出新的檢索方式來加速檢查的速度， 質因數分解 。 這個我會讓我來~ 圖/ Ron Armstrong @ Wikimedia Commons 透過短除法，可以得到30的質因數分解如下: 然後回到1至25，便可以馬上 剔除不與30互質的數字 ，也就是2的倍數、3的倍數以及5的倍數。因為，當該數字為2的倍數時，該數字與30便至少有2為他們的公因數。3的倍數與5的倍數，同理。 再進階些，可以使用 排容原理 : 我們讓圖中A、B、C區塊分別代表25裏頭2的倍數、3的倍數以及5的倍數，是故，A與B的交集(紅色與藍色的重疊區塊)即是那些同時為2的倍數也是3的倍數的那些數字，比如說6、12、18、24，可以發現，也就是6的倍數。 所以，計算25以內與30互質的個數，除了一個個檢查互質以外，也可以透過反面的想法，剔除所有不互質的數，剩下的便是與30互質的數了! 從上圖可以發現，整個不互質的數的區塊為(A區塊+B區塊+C區塊)再扣除重疊的(A與B區塊)、(A與C區塊)以及(B與C區塊)最後再加回(A與B與C區塊)，也就是... |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| 實際上操作看看: |A|=25以內2的倍數個數=(25 ÷2)取整數=12 |B|=25以內3的倍數個數=(25 ÷3)取整數=8 |C|=25以內5的倍數個數=(25 ÷5)取整數=5 |A∩B| =25以內6的倍數個數=(25 ÷6)取整數=4 |A∩C| =25...