# Solution For Count Primes

The Count Primes problem on LeetCode asks us to count the number of prime numbers less than a given non-negative integer n.

To solve this problem, we can use the Sieve of Eratosthenes algorithm, which is an efficient algorithm for finding all prime numbers up to a given limit. The algorithm works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

Here is the detailed solution in Python:

“`
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0

``````    # initialize a boolean array to mark all numbers as potential prime
is_prime = [True] * n
is_prime = is_prime = False

# iterate over the numbers up to the square root of n
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
# mark the multiples of i as composite
for j in range(i * i, n, i):
is_prime[j] = False

# count the number of primes
return sum(is_prime)
``````

“`

We start by checking if n is less than or equal to 2, in which case there are no primes less than n. Otherwise, we initialize a boolean array is_prime of length n, where is_prime[i] represents whether i is prime or not. We then mark 0 and 1 as not prime, since they are not considered to be prime.

Next, we iterate over the numbers up to the square root of n, since any composite number less than n must have a prime factor less than or equal to its square root. For each prime number i, we mark its multiples as composite by iterating over all multiples i * j less than n and setting is_prime[i * j] to False. Note that we start marking the multiples of i from i * i, since any multiple less than i * i would have already been marked by a smaller prime factor.

Finally, we count the number of primes by summing the values in the is_prime array that are True.

The time complexity of this solution is O(n * log(log(n))), which is the time it takes to perform the Sieve of Eratosthenes algorithm. The space complexity is O(n) for the is_prime array.

## Step by Step Implementation For Count Primes

```public int countPrimes(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
if (isPrime(i)) {
count++;
}
}
return count;
}

private boolean isPrime(int num) {
if (num <= 1) return false;
// Loop's ending condition is i * i <= num instead of i <= sqrt(num)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}```
```def countPrimes(n: int) -> int:
if n <= 2:
return 0

primes = [True] * n
primes = primes = False

for i in range(2, n):
if primes[i]:
for j in range(i*i, n, i):
primes[j] = False

return sum(primes)```
```//Solution:

function countPrimes(n) {
let count = 0;

for (let i = 1; i < n; i++) {
if (isPrime(i)) {
count++;
}
}

return count;
}

function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true;
if (num % 2 === 0) return false;

for (let i = 3; i <= Math.sqrt(num); i += 2) {
if (num % i === 0) {
return false;
}
}

return true;
}```
```int countPrimes(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
if (isPrime(i)) {
count++;
}
}
return count;
}

bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}```
```public int CountPrimes(int n) {
if (n <= 2) return 0;

// create an array of booleans
// initially all set to true
bool[] isPrime = new bool[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}

// for each number i, check if i is a prime number
// if so, set all its multiples to false
for (int i = 2; i < Math.Sqrt(n); i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}

// finally, count how many numbers are prime
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}

return count;
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]