1 頁 (共 1 頁)

駭客數學p1-17

發表於 : 2013年 8月 15日, 13:24
gncpkat
在101到500之間共有400個正整數,其中和12互質的數共有幾個?
(A)130 (B)132 (C)134 (D)136
答案:C

Re: 駭客數學p1-17

發表於 : 2013年 8月 15日, 14:26
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

Re: 駭客數學p1-17

發表於 : 2013年 8月 15日, 14:46
gncpkat
謝謝您

Re: 駭客數學p1-17

發表於 : 2021年 7月 20日, 16:16
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 個 呢?

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

Re: 駭客數學p1-17

發表於 : 2021年 7月 21日, 10:11
thepiano
1 ~ 500 的正整數中,與 12 互質的有 167 個
包括 1,5,7,11,13,......

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

Re: 駭客數學p1-17

發表於 : 2021年 7月 22日, 22:42
Yinong024618
謝謝鋼琴老師
我了解了,
也就是說1~500與12互質的數是167個,
且1~100與12互質的數是33個。
這33個包含在167個互質的書當中當中,且範圍在1~100裡面。

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

:redface: