LeetCode204 Count Primes

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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

样例

1

思路

统计前$n$个数中有多少个素数。

可以用Eratosthenes筛法Euler筛法,详见素数筛法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int countPrimes(int n) {
bool* isPrime = new bool[n];
fill(isPrime, isPrime+n, true);
int ans = 0;
for (int i = 2; i < n; ++i) {
if (isPrime[i]) {
ans++;
for (int j = 2*i; j < n; j += i) isPrime[j] = false;
}
}
return ans;
}
};
分享到 评论