文章目录

1. 1. Count Prime
   1. 1.1. 暴力法
   2. 1.2. 筛法

Count Prime

---

题目挺直白的，就是求小于给定非负整数的质数数量。

暴力法

---

我最先想到就是判断该非负整数是否可以整除2到它的平方根。如果从2到平方根均不能被整除，那么该数就是质数。结果很明显，这个方法肯定会超时。复杂度是O( n*sqrt(n) )。

筛法

---

接着就用稍微高级一点的筛法来求，思路是如果某个数是质数了，那么它的倍数肯定不是质数。利用这个思想就逐步往上判断。

在网上搜索了一下，发现筛法的复杂度是O(n*loglogn)，具体证明就不写了。

因为两个方法的思路都很简单，所以我就不给出伪代码了。