駭客數學p1-17

[gncpkat]

在101到500之間共有400個正整數，其中和12互質的數共有幾個？
(A)130 (B)132 (C)134 (D)136
答案：C

[thepiano]

先求 1 ~ 500 的正整數中，與 12 互質的有幾個

12 有 2 個質因數，2 和 3
與 12 互質，表示此數不含質因數 2 或 3，也就是非 2 的倍數或 3 的倍數

以下的中括號是高斯記號，[a] 表示不大於 a 的最大整數
1 ~ 500 的正整數中，2 的倍數有 [500/2] = 250 個
1 ~ 500 的正整數中，3 的倍數有 [500/3] = 166 個

6 的倍數在扣掉 2 的倍數和扣掉 3 的倍數時，重複扣了一次，所以要加回來
1 ~ 500 的正整數中，6 的倍數有 [500/6] = 83 個

1 ~ 500 的正整數中，與 12 互質的有 500 - [500/2] - [500/3] + [500/6] = 167 個

同理，1 ~ 100 的正整數中，與 12 互質的有 100 - [100/2] - [100/3] + [100/6] = 33 個

所求 = 167 - 33 = 134

[gncpkat]

謝謝您

[Yinong024618]

thepiano老師您好，我想請問這一題計算的問題，計算到

1 ~ 500 的正整數中，與 12 互質的有 500 - [500/2] - [500/3] + [500/6] = 167 個

能夠理解，但是為什麼之後不是減去100，(因為設想減去100個的緣故)
而是減去 1 ~ 100 的正整數中，與 12 互質的有 100 - [100/2] - [100/3] + [100/6] = 33 個 呢?

這是我計算的盲點，希望老師可以解惑，謝謝您

[thepiano]

1 ~ 500 的正整數中，與 12 互質的有 167 個
包括 1，5，7，11，13，......

如果您減去 100，就是 1，2，3，4，5，......，100 這些都減去了
問題是 2，3，4，6，......，100 不在上面的 167 個中啊

[Yinong024618]

謝謝鋼琴老師
我了解了，
也就是說1~500與12互質的數是167個，
且1~100與12互質的數是33個。
這33個包含在167個互質的書當中當中，且範圍在1~100裡面。

題目限定101~500間400個正整數中和12互質的數字，
所以要將167-33得到在這400正整數裡與12互質的數字。