[LeetCode] Count Primes

Description: Count the number of prime numbers less than a non-negative number, n

解题思路

采用Eratosthenes筛选法，依次分别去掉2的倍数，3的倍数，5的倍数，……，最后剩下的即为素数。

实现代码:int countPrimes(int n) {int count = 0;bool *b = new bool[n];b[2] = true; //2是偶数，但不能被筛掉，，需要特殊考虑for (int i = 3; i < n; i++){if (i & 1){b[i] = true; //奇数}else{b[i] = false;}}for (int i = 2; i < n; i++){if (b[i]){count++;for (int j = 2; j * i < n; j++){b[i * j] = false;}}}delete [] b;return count;}};

明天的希望，让我们忘了今天的痛苦