Finding all prime numbers within a range

Question

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?

The logic I am following in this code is make a list of all primes I have found. Then check that every odd number less than 2,000,000 is not divisible by any of the primes in my list. If that is the case I am calling the number prime.

package main 
import ("fmt" 
"time" 
) 
func find_primes(max int) []int { 
 // list of all primes that we find 
 var primes []int 
 primes = append(primes, 2) 
 var is_prime = true 
 for i:=3; i<=max; i++ { 
 is_prime = false 
 // only odds can be prime 
 if i%2 != 0 { 
 is_prime = true 
 // should not be divisible by any previous
 // prime numbers 
 for _, x := range primes { 
 if i%x == 0 { 
 is_prime = false 
 break 
 } 
 } 
 } 
 if is_prime { 
 primes = append(primes, i) 
 } 
 } 
 return primes 
} 
// just sume up all of the primes 
func sum_primes(primes []int) int { 
 var total int = 0 
 for _, x := range primes { 
 total = total + x 
 } 
 return total 
} 
func main() { 
 start := time.Now() 
 // find all primes less than 2,000,000 
 primes := find_primes(2000000) 
 sum := sum_primes(primes) 
 fmt.Println(sum) 
 t := time.Now() 
 elapsed := t.Sub(start) 
 fmt.Println(elapsed) 
} 

Answer 1

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

---

Go was designed for Google scale. Therefore, Go package testing includes benchmarking tools. For example,

$ go test -bench=. -benchmem
BenchmarkPeterSO-8 500 3805125 ns/op 1007621 B/op 1 allocs/op
BenchmarkNightman-8 1 95703259026 ns/op 5866752 B/op 31 allocs/op
$ 

---

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.

• Martin R: 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.