Count primes ---ACM 题目

Question

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

Answer 1

举个例子吧：比如算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个
自己多想想就好了