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 | class Solution { |
Java 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class 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
18class 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/