6 of 7 added 95 characters in body

I am trying to find all primes less than 2,000,000 and sum them together. My code currently takes 1'36" to run. Is there a faster way to get my solution?


Yes. For example,

142913828922
3.860761ms

versus your

142913828922
1m35.090248409s

prime.go:

package main

import (
    "fmt"
    "time"
)

const (
    prime    = 0x00
    notprime = 0xFF
)

func oddPrimes(n uint64) (sieve []uint8) {
    sieve = make([]uint8, (n+1)/2)
    sieve[0] = notprime
    p := uint64(3)
    for i := p * p; i <= n; i = p * p {
        for j := i; j <= n; j += 2 * p {
            sieve[j/2] = notprime
        }
        for p += 2; sieve[p/2] == notprime; p += 2 {
        }
    }
    return sieve
}

func sumPrimes(n uint64) uint64 {
    sum := uint64(0)
    if n >= 2 {
        sum += 2
    }
    for i, p := range oddPrimes(n) {
        if p == prime {
            sum += 2*uint64(i) + 1
        }
    }
    return sum
}

func main() {
    start := time.Now()

    var n uint64 = 2000000 - 1
    sum := sumPrimes(n)
    fmt.Println(sum)

    fmt.Println(time.Since(start))
}

Reference: Sieve of Eratosthenes - Wikipedia


Comment: You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. – Martin R


The thought process is simple, obvious, and well-known.

The prime number problem is well-known.

Therefore, Standing on the shoulders of giants - Wikipdia.

"If I have seen further it is by standing on the sholders [sic] of Giants." Isaac Newton

For example, Sieve of Eratosthenes - Wikipedia.

The algorithm given in the question is much slower than Eratosthenes' well-known algorithm, approximately 25,000 times slower.

In real-world code reviews, code should be correct, maintainable, robust, reasonably efficient, and, most importantly, readable. The code in the question is not reasonably efficient.