NUHMAN.com

Problem Statement

Given an integer n, return the number of prime numbers that are strictly less than n.

Function Signature:

go

func countPrimes(n int) int

Example 1:

go

fmt.Println(countPrimes(10)) // Output: 4

Explanation: There are 4 prime numbers less than 10: 2, 3, 5, 7.

Example 2:

go

fmt.Println(countPrimes(0))  // Output: 0

Explanation: There are no prime numbers less than 0.

Example 3:

go

fmt.Println(countPrimes(1))  // Output: 0

Explanation: There are no prime numbers less than 1.

Constraints:

• 0 <= n <= 5 * 10^6

Approach

We need to count all prime numbers strictly less than n. To efficiently solve this problem, we can use the Sieve of Eratosthenes algorithm. This algorithm is ideal for generating all prime numbers up to a given number and works as follows:

1. Initialization:

• Create a boolean array isPrime[] of size n. Initially, all elements in the array are marked as true.
• Mark 0 and 1 as false since they are not prime numbers.

1. Sieve Process:

• Start from the first prime number 2. For every number i, if i is marked as prime (isPrime[i] = true), mark all multiples of i (greater than or equal to i^2) as non-prime (false).
• Continue this process for all numbers up to sqrt(n).

1. Counting Primes:

• After applying the sieve, the numbers that remain true in the isPrime[] array represent prime numbers. We can count them to get the result.

Time Complexity:

• The Sieve of Eratosthenes algorithm has a time complexity of O(n log log n), which is efficient for large values of n (up to 5 * 10^6).

Go Implementation

go

package main

import "fmt"

// Function to count primes less than n using the Sieve of Eratosthenes
func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    // Create a boolean array isPrime with all entries set to true
    isPrime := make([]bool, n)
    for i := 2; i < n; i++ {
        isPrime[i] = true
    }

    // Apply the sieve of Eratosthenes
    for i := 2; i*i < n; i++ {
        if isPrime[i] {
            for j := i * i; j < n; j += i {
                isPrime[j] = false
            }
        }
    }

    // Count the number of primes
    count := 0
    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }

    return count
}

func main() {
    // Example 1
    fmt.Println(countPrimes(10)) // Output: 4

    // Example 2
    fmt.Println(countPrimes(0))  // Output: 0

    // Example 3
    fmt.Println(countPrimes(1))  // Output: 0
}

Explanation of the Code:

1. countPrimes Function:

• Input: The function takes an integer n.
• Initial Check: If n <= 2, there are no primes less than n, so we return 0.
• Boolean Array (isPrime): We create an array isPrime of size n, initialized to true. All numbers starting from 2 are assumed to be prime.
• Sieve of Eratosthenes: We loop over all numbers starting from 2 up to sqrt(n). For each prime number i, we mark all its multiples as non-prime.
• Count Primes: After the sieve, the isPrime[] array contains true for prime numbers. We count these true values and return the count.

2. Main Function:

• The main function tests the countPrimes function with a few sample test cases.

Example Walkthrough

Example 1:

Input:

go

fmt.Println(countPrimes(10))

• The prime numbers less than 10 are: 2, 3, 5, 7.
• The function should return 4.

Output: 4

Example 2:

Input:

go

fmt.Println(countPrimes(0))

• There are no primes less than 0.

Output: 0

Example 3:

Input:

go

fmt.Println(countPrimes(1))

• There are no primes less than 1.

Output: 0

Conclusion

The LeetCode 204: Count Primes problem is efficiently solved using the Sieve of Eratosthenes algorithm, which allows us to count prime numbers up to n in O(n log log n) time. This is efficient enough to handle the constraint of n being as large as 5 * 10^6.

This solution provides a clear and efficient approach to count primes in a given range.