Description#
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:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def countPrimes(self, n: int) -> int:
primes = [True] * n
ans = 0
for i in range(2, n):
if primes[i]:
ans += 1
for j in range(i + i, n, i):
primes[j] = False
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int countPrimes(int n) {
boolean[] primes = new boolean[n];
Arrays.fill(primes, true);
int ans = 0;
for (int i = 2; i < n; ++i) {
if (primes[i]) {
++ans;
for (int j = i + i; j < n; j += i) {
primes[j] = false;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int countPrimes(int n) {
vector<bool> primes(n, true);
int ans = 0;
for (int i = 2; i < n; ++i) {
if (primes[i]) {
++ans;
for (int j = i; j < n; j += i) primes[j] = false;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func countPrimes(n int) int {
primes := make([]bool, n)
for i := range primes {
primes[i] = true
}
ans := 0
for i := 2; i < n; i++ {
if primes[i] {
ans++
for j := i + i; j < n; j += i {
primes[j] = false
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /**
* @param {number} n
* @return {number}
*/
var countPrimes = function (n) {
let primes = new Array(n).fill(true);
let ans = 0;
for (let i = 2; i < n; ++i) {
if (primes[i]) {
++ans;
for (let j = i + i; j < n; j += i) {
primes[j] = false;
}
}
}
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
public int CountPrimes(int n) {
var notPrimes = new bool[n];
int ans = 0;
for (int i = 2; i < n; ++i)
{
if (!notPrimes[i])
{
++ans;
for (int j = i + i; j < n; j += i)
{
notPrimes[j] = true;
}
}
}
return ans;
}
}
|
