Problem:
Count the number of prime numbers less than a non-negative number, n.
Summary:
判断小于某非负数n的质数个数。
Solution:
用所谓的“刷质数表”的方式先用HashTable记录小于n的所有数是质数还是合数，再逐一数出。
看了题目中的Hint才知道这种方法有一个更加高大上的名字Sieve of Eratosthenes
即在每判断一个数为质数时，将它的bei'shu倍数均计为合数。
class Solution {
public:
int countPrimes(int n) {
if (n == || n == ) {
return ;
}
vector<int> prime(n, );
prime[] = prime[] = ;
for (long long i = ; i < n; i++) {
if (!prime[i]) {
for (long long j = i * i; j < n; j += i) {
prime[j] = ;
}
}
}
int cnt = ;
for (int i = ; i < n; i++) {
if (!prime[i]) {
cnt++;
}
}
return cnt;
}
};