204. Count Primes

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:

• 0 <= n <= 5 * 106

Solutions

• 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;
}
}

• 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;
}
};

• 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

• 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
}

• /**
* @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;
};

• 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;
}
}