Sieve of Eratosthenes: Accelerating the "crossover" step

php Xiaobian Apple introduces to you the sieve of Eratosthenes, which is an algorithm for quickly calculating prime numbers. This algorithm filters out all prime numbers by continuously excluding multiples of non-prime numbers. Compared with the traditional method of judging prime numbers one by one, the Sieve of Eratosthenes method can greatly speed up the calculation process. Its core idea is to traverse from 2 to n, marking each multiple of prime number p as a non-prime number until the traversal is completed. This method performs well when calculating large numbers of prime numbers and is an efficient prime number calculation algorithm.

Question content

I have implemented a function that lists 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 found an inefficiency: i.e. CrossOffMultiples was called more times than necessary. IOW, an integer that has been "crossed out" will be crossed out a second or third time (or even more), because any multiple m will have multiple factors dividing it. But I can't seem to figure out how to leverage this bit of information to allow me to reduce the number of calls to CrossOffMultiples. I'm sure there is a way to do this, but for some reason I can't.

Any suggestions?

Workaround

If you reduce the number of times CrossOffMultiples is called, i.e. you don't call it on some primes p, then p * p will not be crossed out. But what you can do is start the loop from p * p instead of 2 * p.

It is normal to cross out numbers multiple times, and this is what the Sieve of Eratosthenes did. Linear Sieve Method is a similar algorithm that may be of interest to you. p>

The above is the detailed content of Sieve of Eratosthenes: Accelerating the "crossover" step. For more information, please follow other related articles on the PHP Chinese website!