作者neqwxyyyz (查加油)
看板Math
標題[中學] 因倍數的互質個數問題
時間Tue Jul 5 09:43:21 2011
請問各位幾個問題
(1).正整數1到1000中，與2和3和5皆互質的數有幾個?
(2).正整數1000到2000中，與2和3和5皆互質的數有幾個?
用不同算法算 似乎答案都不一樣
到底是266還是267 我甚至還有算到268個
煩請大家幫我解惑了 謝謝
我的算法就第一題而言 似乎沒有問題了
但是第二題就怪怪的了
1000到2000共1001個數
算法一:[1001*(1/2)*(2/3)*(4/5)]=266
算法二:1001-[1001/2]-[1001/3]-[1001/5]-[1001/6]-[1001/10]-[1001/15]-[1001/30]
=1001-500-333-200+166+100+66-33
=267
算法三:[2000*(1/2)*(2/3)*(4/5)]-[1000*(1/2)*(2/3)*(4/5)]
=266
算法四:把算法二的1001改成2000和1000算出來的值再相減
534-266=268
看起來似乎都對 到底哪裡出問題了?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.81.227.110
1F：推 FocusE :1000-(500+333+200-166-66-100+33)=266 07/05 10:04
2F：→ FocusE :1001-(501+333+201-167-67-101+33)=268 07/05 10:04
3F：→ FocusE :應該沒錯 07/05 10:05
4F：→ welf :其實你可以把 你所謂"不同算法"po出來讓大家看看 07/05 10:33
※ 編輯: neqwxyyyz 來自: 219.81.227.110 (07/05 11:33)
5F：推 FocusE :正常來說要算1000到2000 2,3,5互質的數 07/05 12:02
6F：→ FocusE :要用1~2000的個數 減去 1~999的個數 07/05 12:03
7F：→ FocusE :不能直接拿1001個來算 比如 2的倍數你算500 07/05 12:03
8F：→ FocusE :事實上1000~2000 2的倍數有501個 07/05 12:04