204. Count Primes
Đề Bài
Given an integer n, return the number of prime numbers that are strictly less than n.
Example 1:
Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 0
Constraints:
0 <= n <= 5 * 106
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0204-count-primes.cpp
class Solution {
public:
int countPrimes(int n) {
vector<bool> dp(n + 1, false);
for (int i = 2; i < n; ++i) {
dp[i] = true;
}
for (int i = 2; i < n; ++i) {
if (!dp[i]) {
continue;
}
for (int j = 2*i; j < n; j += i) {
dp[j] = false;
}
}
int cnt = 0;
for (int i = 2; i < n; ++i) {
cnt += dp[i];
}
return cnt;
}
};