204. Count Primes
給定一個整數 n，返回小於 n 的質數數量。
範例：
輸入：n = 10
輸出：4
解釋：小於 10 的質數有 4 個，分別是 2、3、5 和 7。
Python
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
# Initialize a list to mark non-prime numbers
is_prime = [True] * n
is_prime[0], is_prime[1] = False, False # 0 and 1 are not primes
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n, i):
is_prime[j] = False
# Count the number of primes
return sum(is_prime)
55.34MB, 1214ms
C++
class Solution {
public:
int countPrimes(int n) {
if (n <= 2) {
return 0;
}
// Initialize a vector to mark non-prime numbers
std::vector<bool> is_prime(n, true);
is_prime[0] = is_prime[1] = false; // 0 and 1 are not primes
for (int i = 2; i * i < n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j < n; j += i) {
is_prime[j] = false;
}
}
}
// Count the number of primes
int count = 0;
for (int i = 2; i < n; ++i) {
if (is_prime[i]) {
++count;
}
}
return count;
}
};
11.81MB, 429ms
Javascript
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
if (n <= 2) {
return 0;
}
// Initialize an array to mark non-prime numbers
const isPrime = new Array(n).fill(true);
isPrime[0] = isPrime[1] = false; // 0 and 1 are not primes
for (let i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (let j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
// Count the number of primes
let count = 0;
for (let i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
};
90.15MB, 280ms
