# Finding all prime numbers within a range

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
}
}

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)
}


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 = 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.

"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.

• 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 Jan 23 '19 at 7:48