204. Count Primes(埃拉托色尼）

Description: Count the number of prime numbers less than a non-negative number, n. Credits: Special thanks to @mithmatt for adding this problem and creating all test cases. class Solution { public: int countPrimes(int n) { if(n <= 2) return 0; vector<int> prime(n+1, -1); for(int i=2; i<sqrt(n); ++i){ if(prime[i] != 0){ int p = i + i; while(p < n){ prime[p] = 0; p += i; //这里是+i,不要写走眼 } } } int count = 0; for(int i=2; i<n; ++i){ if(prime[i] != 0) ++count; } return count; } };