2 wr technology WR_technology 于 2016.09.20 13:30 提问

Count primes ---ACM 题目

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5901
AC代码: http://www.cnblogs.com/TAT1122/p/5883884.html
很不理解是什么原理.求大牛讲讲是根据什么来解出的这道题.谢谢 本问题是ACM题目.

1个回答

genglanggenglang
genglanggenglang   2016.09.20 14:14

举个例子吧:比如算100以内的质数个数,
首先,列出100开平方,也就是10以内的所有质数
2,3,5,7
然后
N0 = 100
N1 = 1+N0-N0/2 = 1+100-100/2 = 51 (去除2的倍数后的个数)
N2 = 1+N1-N1/3 = 1+51-51/3 = 1+51-17=35 (去除3的倍数后的个数)
N3 = 1+N2-N2/5 = 1+35-35/5 = 1+35-7 = 29 (去除5的倍数后的个数)
N4 = 1+N3-N3/7 = 1+29-29/7 = 1+29-4 = 26 (去除7的倍数后的个数)
个数 K=N4-1=25, (剩下的数字中,1不是质数)
答案: 25个
自己多想想就好了

WR_technology
WR_technology 请问你是想用容斥定理?
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!