2
\$\begingroup\$

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)                              
}   
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Martin R Jan 23 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.