Sum of primes in given range in Go

Question

This piece of code calculates the sum of all prime numbers below 1 million.

It stood out to me that the Ruby script is around 20% faster. I know that Go should be faster just for being a compiled language. So how can I make the Go code run faster than it already does?

I'm interested in solutions involving goroutines, pointers, both, etc.

In Go:

Execution time: ~4.6s

package main

import (
    "fmt"
    "time"
)

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

    // Create slice containing values from 0 to 1 million
    a := []int{}
    for i := 0; i < 1000000; i++ {
        a = append(a, i)
    }

    done := false
    factor := 1
    for !done {
        // Get the next factor to be used as a filter for slice `a` 
        factor = nextPrime(a, factor)

        var modified bool
        // Filtering slice `a`
        for i, v := range a {
            if v%factor == 0 && v > factor {
                a[i] = 0 // This is equivalent to eliminating the value
                modified = true
            }
        }

        if !modified {
            done = true
        }
    }

    var sum int
    for _, v := range a {
        sum += v
    }
    fmt.Println(sum - 1)

    t2 := time.Now()
    fmt.Println("Execution duration:", t2.Sub(t1))
}

// Doesn't return a prime literaly, but the least value to be used
// to filter out non prime numbers from an array or slice
func nextPrime(a []int, factor int) (newFactor int) {
    for _, v := range a {
        if v > factor {
            newFactor = v
            break
        }
    }
    return
}

In Ruby:

Execution time: ~3.5s

t1 = Time.now

def next_prime(a, t)
  a.each { |m| return m if m > t }
end

a=(2..999_999).to_a

complete = false

until complete
  t ||= 1
  t = next_prime(a, t)
  presize = a.size
  a.map! { |m| m%t == 0 && m > t ? nil : m }
  a.compact!
  complete = true if a.size == presize # when factoring stops shortening the array, we're done
end

r = 0
a.each { |m| r+=m }
puts r

t2 = Time.now
puts t2 - t1

Answer 1

I don't know Ruby, and cannot infer how similar are the algorithms (if they are significantly different, there is no sense to compare performance). However I can point some performance problems in the go code.

The range loop

    for i, v := range a {
        if v%factor == 0 && v > factor {
            a[i] = 0
            modified = true
        }
    }

does a lot of unnecessary tests. A (more controlled) for loop seems to suite better:

    for i := factor*factor; i < 10000000; i += factor {
        a[i] = 0
    }

---

The search for next prime starts from the very beginning of a - rendering the search effectively quadratic. There is no need to search an initial [0, factor] slice; start with factor + 1:

    for _, v := range a[factor + 1:] {