LeetCode 204. Count Primes
程序员文章站
2024-03-21 15:06:10
...
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Sieve of Eratosthenes算法图解:
C++
class Solution {
public:
int countPrimes(int n) {
bool Hash[n+1];
memset(Hash, true, n+1);
for(int i = 2; i * i < n; i++){
if(Hash[i]){
for(int j = i * i; j < n; j += i){
Hash[j] = false;
}
}
}
int cnt = 0;
for(int i = 2; i < n; i++){
if(Hash[i]) cnt++;
}
return cnt;
}
};
Java
class Solution {
public int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
for(int i = 2; i * i < n; i++){
if(isPrim[i]){
for(int j = i * i; j < n; j += i){
isPrim[j] = false;//排除所有质数的倍数
}
}
}
int cnt = 0;
for(int i = 2; i < n; i++){
if(isPrim[i]) cnt++;
}
return cnt;
}
}
Python
class Solution(object):
def countPrimes(self, n):
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes)
上一篇: KITTI数据集介绍