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

• Phrancis: @sargas Code Review regulars are generally not fond of "A vs. B" questions, as those are more likely to be relevant prior to the code being written (or implemented), as opposed to code review time. Mind you, we can still review your code, but it's possible you will get down-votes for this reason.
• RubberDuck: @sargas more or less what Phrancis said. I tend to simply ignore A vs B questions, but I knee jerked with a vote when I saw one in two different languages. I was going to vote to close as too broad because of it. I missed the part where you were only asking for a review of the Go. I added some quote blocks to clarify which code should be reviewed. Honestly, thanks for pinging me, because I was mistaken.
• sargas: @RubberDuck Thanks for helping me edit this into a more clear question. Should I still remove to Ruby portion of the question? I still thinks it is relevant since I'd like to know how I can improve the Go solution into a faster version. Perhaps using pointers rather than copies?
• RubberDuck: @sargas I'd leave it. You're right. It is relevant. Unfortunately, I don't know Go, so I won't be of much help on that front. Sorry again for my misunderstanding.
• sargas: @RubberDuck I can only thank you for the help and the positive attitude.

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:] { 

• sargas: This solution got the execution time down to 54ms! I'm assuming i := factor*factor still causes the loop to revisit some indexes of a, but the revisits are way less than scanning the entire array?