0%

leetcode Count Primes

leetcode Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n. 题目地址 : leetcode Count Primes

思路:

朴素的判断必定超时,我们每次判断一个数是素数的时候,就将它的倍数标记为非素数即可。

下面附上c++  python 和 java代码

Code

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int countPrimes(int n) {
if (n <= 2) return 0;
bool * isPrimer = new bool[n];
for (int i = 0; i < n; i++) isPrimer[i] = true;
for (int i = 2; i * i < n; i++) {
if (isPrimer[i])
for (int j = i ; j * i < n; j ++)
isPrimer[j * i] = false;
}
int res = 0;
for (int i = 2; i < n; i++)
if (isPrimer[i]) res++;
delete[] isPrimer;
return res;
}
};

 

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int countPrimes(int n) {
if (n <= 2) return 0;
boolean[] vis = new boolean[n];
for (int i = 2; i * i < n; i++) {
if (vis[i]) continue;
for (int j = i; j * i < n; j++)
vis[i * j] = true;
}
int ans = 0;
for (int i = 2; i < n; i++)
if (!vis[i]) ans++;
return ans;
}
}

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2: return 0
vis = [False] * n
for i in range(2, int(n ** 0.5) + 1):
if vis[i]: continue
j = i
while j * i < n:
vis[j * i] = True
j += 1
ans = 0
for i in range(2, n):
if not vis[i]: ans += 1
return ans

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~