10000 以内，与 10000 互质的正整...

[单选题]

10000 以内，与 10000 互质的正整数有（）个。

查看答案及解析

干草块~

这是一个简单的容斥原理，首先如果一个数a与10000有大于1的公因数x，那么x必然可以被质因数分解为一些质数的乘积，也就是说只有当a和10000有至少一个相同的质因子的时候，他们之间才会有大于1的公因数。

之后，我们可以对10000分解质因数，分解出来只有2和5。与10000互质的数的个数=数的总数-不与10000互质的数的个数

再考虑1-10000有多少个数里面有2这个质因子，显然有10000/2=5000个（可以举几个例子如1-15,1-20来理解），以此类推，有10000/5=2000个数里面有5这个质因子。

但是答案并不是10000-2000-5000=3000，为什么？因为像10、20这样既有2这个质因子也有5这个质因子的数既被2统计到又被5统计到了。也就是有10这个因子的数被统计到了两次，加上这些数的个数10000/10=1000，就是最后的答案4000

发表于 2021-08-31 20:30:43 回复(1)

ImXiu

10000大致的因数就是2和5（其余的因数都是这两个数的倍数），10000以内的2的倍数大约有5000个，5的倍数有2000个，但是由于其中有一半是2的倍数，所以有1000+5000=6000个，10000再去掉6000个，就是4000

发表于 2019-10-03 15:56:10 回复(1)

Crawler201908052222442

简单方法程序枚举

只能被自身和2相除的数

发表于 2019-08-06 15:19:13 回复(1)

提交观点

问题信息

普及数学

上传者：牛客309901号

难度：

3条回答 0收藏 5505浏览

扫一扫，把题目装进口袋