本文共 1257 字，大约阅读时间需要 4 分钟。
Description:Count the number of prime numbers less than a non-negative number, n
分析：
题目要求计算小于N的所有素数的个数。所有主程序很简单：判断是否是素数字，如是，count++ （暂且忽略prim_vec, 后面判断素数时会用到）：
int countPrimes(int n) { int i =0, count=0; for (i=1; i 判断是否是素数，最简单的代码如下，但这样提交时会超时。 bool isprime(int n) { if (n < 2) return false; if (n ==2 ) return true; int tmp = sqrt(n); for (int i=1; i 对算法进行改进，将判断能否被小于sqrt（n）的数整除，改为能否被小于sqrt(n)的素数整除，可以节省很多计算量，大大减少计算的次数。这样就需要将以前计算的素数都记下来，所以使用一个全局的vector prim_vec 来记录计算过的素数。 对素数的判断代码改进如下：
vector prim_vec; bool isprime(int n) { if (n < 2) return false; if (n == 2) return true; if(n %2 == 0) return false; int sq = sqrt(n); int len = prim_vec.size(); for (int index=0; index sq) break; if (n % tmp == 0) return false; } return true; } 题目完整代码如下：
class Solution {public: vector prim_vec; bool isprime(int n) { if (n < 2) return false; if (n == 2) return true; if(n %2 == 0) return false; int sq = sqrt(n); int len = prim_vec.size(); for (int index=0; index sq) break; if (n % tmp == 0) return false; } return true; } int countPrimes(int n) { int i =0, count=0; for (i=1; i 转载地址：http://kfxti.baihongyu.com/