Golang solution (16ms) - Sieve of Eratosthenes


  • 0
    func countPrimes(n int) int {
        if n < 2 {return 0}
        table := make([]bool, n + 1)
        table[0], table[1] = true, true
        for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
            if table[i] {continue}
            for j := i * i; j < n; j += i {
                table[j] = true
            }
        }
        numPrimes := 0
        for i := 2; i < n; i++ {
            if !table[i] {numPrimes++}
        }
        return numPrimes
    }
    

    Here is an alternative approach that does the counting in one go:

    func countPrimes(n int) int {
        if n < 2 {return 0}
        table := make([]bool, n + 1)
        table[0], table[1] = true, true
        numPrimes := 0
        for i := 2; i < n; i++ {
            if table[i] {continue}
            numPrimes++
            for j := i * i; j < n; j += i {
                table[j] = true
            }
        }
        return numPrimes
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.