Count the number of prime numbers less than a non-negative number, n.
问题：找出所有小于 n 的素数。
题目很简洁，但是算法实现的优化层次有很多层。其中最主要思想的是采用 Sieve of Eratosthenes 算法来解答。
大思路为：
如何找到 n 范围内所有合数？
将第一个素数 2 赋值给 i。
当 i 小于 n 时：（2）
上面算法有可以优化的地方：
(1)步骤找合数，无需从 2 开始算 i 的倍数，而是从 i 倍开始算，即 i*i。举个例子，当 i 为 5 时， 5*2, 5*3, 5*4 的记号，已经在 i 分别为 2,3,4的时候做了。所以，可以直接从 i 倍开始算。相应地，(2)步骤也可以优化 “为 i*i < n 时”。
1 int countPrimes(int n) { 2 3 vector<bool> res(n, true); 4 5 for(long i = 2; i * i < n ; i++){ 6 if(res[i] == false){ 7 continue; 8 } 9 10 long square = i*i; 11 for(long k = 0; k * i + square < n ; k++){ 12 res[k * i + square] = false; 13 } 14 } 15 16 int cnt = 0; 17 for(int i = 2; i < n ; i++){ 18 cnt += res[i]; 19 } 20 return cnt; 21 }
[LeetCode] 204. Count Primes 解题思路
原文：http://www.cnblogs.com/TonyYPZhang/p/5138018.html