Description:
Count the number of prime numbers less than a non-negative number, n.
=============
找质数的问题. [http://www.cnblogs.com/li-daphne/p/5549557.html]我在这里有过分析
!!!
利用筛选法的思路,
从2开始的每一个数字i,逐步将数字是i的倍数的数排除在外.
可以利用位图的方法:占用的空间较小
===
code如下:
class Solution { public: int countPrimes(int n) { bitset<10000000> b; for(int i = 0;i<n;i++){ b.set(i,1); } int re = 0; for(int i = 2;i*i<n;i++){ if(b[i]){ for(int k = i;k<(n+1);k = k+i){ if(k==i)continue; b.set(k,0); } }/// }///for for(int i = 2;i<n;i++){ if(b[i]){ re++; } } return re; } };
原文：http://www.cnblogs.com/li-daphne/p/5618418.html