Last updated on October 5th, 2024 at 08:50 pm

Here, We see ** Count Primes LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Hash-Table, Math

## Companies

Amazon, Microsoft

## Level of Question

Medium

**Count Primes LeetCode Solution**

## Table of Contents

**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

**1. Count Primes LeetCode Solution 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; } };

**2. Count Primes LeetCode Solution 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. Count Primes Solution 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 };

**4. Count Primes Solution 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