Count Primes

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

                                            
class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        
        boolean[] isPrime = new boolean[n];
        int count = 0;
        
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                count++;
                for (int j = 2; i * j < n; j++) {
                    isPrime[i * j] = true;
                }
            }
        }
        
        return count;
    }
}

                                            
class Solution(object):
    def countPrimes(self, n):
        if n < 2:
            return 0
        
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                is_prime[i*i:n:i] = [False] * len(is_prime[i*i:n:i])
                
        return sum(is_prime)

                                            
int countPrimes(int n) {
    if (n <= 2) {
        return 0;
    }
    
    int count = 0;
    int *isPrime = (int*)malloc(sizeof(int) * n);
    memset(isPrime, 1, sizeof(int) * n);

    for (int i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = 0;
            }
        }
    }

    for (int i = 2; i < n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }

    free(isPrime);
    return count;
}

                                            
public class Solution {
    public int CountPrimes(int n) {
        if(n <= 2) return 0;
        
        bool[] isPrime = new bool[n];
        for(int i = 2; i < n; i++){
            isPrime[i] = true;
        }
        
        for(int i = 2; i * i < n; i++){
            if(!isPrime[i]) continue;
            for(int j = i * i; j < n; j += i){
                isPrime[j] = false;
            }
        }
        
        int count = 0;
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                count++;
            }
        }
        
        return count;
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
const countPrimes = (n) => {
    if (n <= 2) return 0;
    
    const isPrime = new Array(n).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;
    
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return isPrime.filter((val) => val).length;
};

                                            
function countPrimes(n: number): number {
    if (n <= 2) {
        return 0;
    }

    const isPrime = new Array(n).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.filter((prime) => prime).length;
};

                                            
class Solution {
    /**
     * @param Integer $n
     */
    function countPrimes($n) {
        if ($n <= 2) return 0;
        
        $isPrime = array_fill(0, $n, true);
        $isPrime[0] = $isPrime[1] = false;
        
        for ($i = 2; $i * $i < $n; $i++) {
            if ($isPrime[$i]) {
                for ($j = $i * $i; $j < $n; $j += $i) {
                    $isPrime[$j] = false;
                }
            }
        }
        
        return count(array_filter($isPrime));
    }
}

                                            
class Solution {
    func countPrimes(_ n: Int) -> Int {
        guard n > 2 else {
            return 0
        }
        
        var isPrime = [Bool](repeating: true, count: n)
        isPrime[0] = false
        isPrime[1] = false
        
        var count = 0
        
        for i in 2..<n {
            if isPrime[i] {
                count += 1
                var j = 2
                while i * j < n {
                    isPrime[i * j] = false
                    j += 1
                }
            }
        }
        
        return count
    }
}

                                            
class Solution {
    fun isPrime(num: Int): Boolean {
        if (num <= 1) return false
        for (i in 2 until num) {
            if (num % i == 0) {
                return false
            }
        }
        return true
    }
    
    fun countPrimes(n: Int): Int {
        var count = 0
        for (i in 2 until n) {
            if (isPrime(i)) {
                count++
            }
        }
        return count
    }
}

                                            
class Solution {
  int countPrimes(int n) {
    if (n <= 2) return 0;

    List<bool> isPrime = List.filled(n, true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (int i = 2; i * i < n; i++) {
      if (isPrime[i]) {
        for (int j = i * i; j < n; j += i) {
          isPrime[j] = false;
        }
      }
    }

    int count = 0;
    for (int i = 2; i < n; i++) {
      if (isPrime[i]) count++;
    }

    return count;
  }
}

                                            
func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    isPrime := make([]bool, n)
    count := 0

    for i := 2; i*i < n; i++ {
        if isPrime[i] {
            continue
        }

        for j := i * i; j < n; j += i {
            isPrime[j] = true
        }
    }

    for i := 2; i < n; i++ {
        if !isPrime[i] {
            count++
        }
    }

    return count
}

To solve this coding challenge, the task is to count the number of prime numbers less than a given integer

n

. A prime number is an integer greater than 1 that has no other integer divisors other than 1 and itself.

Explanation

The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a specified integer. It works by iteratively marking the multiples of each prime number starting from 2. Here’s a step-by-step detailed explanation for solving this problem using the Sieve of Eratosthenes method:

Initialization:

Create a list
is_prime

of boolean values. The index of this list represents the number, and the boolean value at that index indicates whether it is prime (
True

) or not (
False

). Initialize the list with
True

values, but specifically mark the indices 0 and 1 as
False

since 0 and 1 are not prime numbers.

Iterate and Mark Non-Primes:

Start iterating from the first prime number, which is 2. For each prime number, mark all of its multiples as
False

, as these multiples cannot be prime.

Continue the Process:

Continue this process up to the square root of
n

because a larger factor of a number will necessarily be a multiple of a smaller factor, which would have been marked earlier.

Count the Primes:

The remaining
True

values in the list
is_prime

indicate prime numbers. The count of
True

values in the list up to
n

will give the number of primes less than
n

.

Let’s break this down into an extensive and detailed pseudocode.

Detailed Steps in Pseudocode

Define Function and Edge Case Check:

If
n

is less than 2, return 0 as there are no prime numbers less than 2.

                                            
function countPrimes(n):
# Check if n is less than 2
if n < 2:
return 0

Create a Boolean List and Initialize:

Create a list called
is_prime

with
n

entries all set to
True

.
Set
is_prime[0]

and
is_prime[1]

to
False

.

                                            
# Initialize is_prime list with True values
is_prime = [True] * n
# Set the indices 0 and 1 to False, since 0 and 1 are not prime
is_prime[0] = False
is_prime[1] = False

Iterate and Mark Non-Prime Numbers:

Iterate over each number starting from
2

to the integer square root of
n

.
For a number at index
i

which is still marked as
True

, mark all its multiples as
False

.

                                            
# Iterate from 2 to sqrt(n)
for i from 2 to sqrt(n) do:
# If i is still considered prime
if is_prime[i]:
# Mark all multiples of i as False (non-prime)
for multiple in range(i * i, n, i):
is_prime[multiple] = False

Count the Prime Numbers:

Sum the
True

values in
is_prime

list to get the count of prime numbers less than
n

.

                                            
    # Count the number of True values in is_prime
    prime_count = sum(is_prime)
    return prime_count

This will effectively give us the number of prime numbers less than

n

using the Sieve of Eratosthenes algorithm. The pseudocode encompasses all necessary steps while iterating and marking non-prime numbers efficiently.