作者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