Sieve of Eratosthenes: speeding up the "cross off multiples" step

I have implemented a function to list prime numbers using the Sieve of Eratosthenes algorithm as follows:

func ListPrimes(n int) []int {
    primeList := make([]int, 0)
    primeBooleans := SieveOfEratosthenes(n)
    for p := 0; p < n+1; p++ {
        if primeBooleans[p] == true {
            primeList = append(primeList, p)
        }
    }
    return primeList
}

func SieveOfEratosthenes(n int) []bool {
    primeBooleans := make([]bool, n+1)
    sqrtN := math.Sqrt(float64(n))
    for k := 2; k <= n; k++ {
        primeBooleans[k] = true
    }
    for p := 2; float64(p) <= sqrtN; p++ {
        if primeBooleans[p] == true {
            primeBooleans = CrossOffMultiples(primeBooleans, p)
        }
    }
    return primeBooleans
}

func CrossOffMultiples(primeBooleans []bool, p int) []bool {
    n := len(primeBooleans) - 1
    for k := 2 * p; k <= n; k += p {
        primeBooleans[k] = false
    }
    return primeBooleans
}

But I’ve spotted an inefficiency: namely, that CrossOffMultiples is being called more times than is necessary. IOW, integers that have already been "crossed off" are getting crossed off a second or third time (or even more) due to the fact that any multiple m is going to have multiple factors that divide it. But what I can’t seem to figure out is how to leverage this bit of information in such a way that allows me to reduce the number of times CrossOffMultiples is called. I’m sure there is a way to do so, but for some reason it’s eluding me.

Any suggestions?

>Solution :

If you reduce the number of times CrossOffMultiples is called, i.e., you don’t call it for some prime p, then p * p won’t get crossed off. But what you can do is start its loop at p * p instead of 2 * p.

It’s normal to cross out numbers multiple times, the sieve of Eratosthenes does that. Linear Sieve is a similar algorithm you might be interested in.