Last updated on January 5th, 2025 at 12:41 am

Here, we see a Count Primes LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Hash-Table, Math

Companies

Amazon, Microsoft

Level of Question

Medium

Count Primes LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Sieve of Eratosthenes”, which is a well-known algorithm for finding all prime numbers up to a given limit.

3. Code Implementation in Different Languages

3.1 Count Primes C++

class Solution {
public:
	int countPrimes(int n) {
		vector<bool> prime(n + 1, true);
		prime[0] = false;
		prime[1] = false;
		for (int i = 2; i * i <= n; i++) {
			if (prime[i]) {
				for (int j = i * i; j <= n; j += i) {
					prime[j] = false;
				}
			}
		}
		int primeCount = 0;
		for (int i = 2; i < n; i++) {
			if (prime[i]) {
				primeCount++;
			}
		}
		return primeCount;
	}
};

3.2 Count Primes Java

class Solution {
    public int countPrimes(int n) {
        boolean[] seen = new boolean[n];
        int ans = 0;
        for (int num = 2; num < n; num++) {
            if (seen[num]) continue;
            ans += 1;
            for (long mult = (long)num * num; mult < n; mult += num)
                seen[(int)mult] = true;
        }
        return ans;
    }
}

3.3 Count Primes JavaScript

var countPrimes = function(n) {
    let seen = new Uint8Array(n), ans = 0
    for (let num = 2; num < n; num++) {
        if (seen[num]) continue
        ans++
        for (let mult = num * num; mult < n; mult += num)
            seen[mult] = 1
    }
    return ans
};

3.4 Count Primes Python

class Solution(object):
    def countPrimes(self, n):
        seen, ans = [0] * n, 0
        for num in range(2, n):
            if seen[num]: continue
            ans += 1
            seen[num*num:n:num] = [1] * ((n - 1) // num - num + 1)
        return ans

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n log log n)	O(n)
Java	O(n log log n)	O(n)
JavaScript	O(n log log n)	O(n)
Python	O(n log log n)	O(n)