Skip to content

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

Solution 1

Thinking

Trial division up to \(\sqrt{x}\) counts primes, but \(n\) can be \(5\times 10^6\), so repeated tests are slow. If \(x\) is prime, its multiples \(2x,3x,\ldots\) are composite.

The Sieve of Eratosthenes marks those multiples as we scan upward, then counts unmarked values. Each composite is crossed off by a factor, in about \(O(n\log\log n)\) time.

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

Comments