LeetCode Count Primes 求素数个数

 1 class Solution {
 2 public:
 3     int countPrimes(int n) {
 4         bool* isPrime =new bool[n] ;
 5         
 6         memset(isPrime,1,n);
 7         
 8         for(int i=2; i*i<n; i++)
 9         {
10             if(!isPrime[i])    continue;
11             for(int j=i*i; j<n; j+=i)    isPrime[j]=0;
12         }
13         int cnt=0;
14         for(int i=2; i<n; i++)    if(isPrime[i])    cnt++;
15         return cnt;
16     }
17 };