Project Euler 10: Summation of primes in Go

Here is my first try at Google's Go language, trying to solve Project Euler Problem 10:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Any suggestions on the style and usage (best practice) of Go?

package main

import "fmt"

var primes = []uint64{2, 3}

func CheckIfIsNewPrime(number uint64) bool {
check_if_number_is_new_prime := false
var remainder uint64 = 0

for i := range primes {
remainder = number % primes[i]
if remainder == 0 {
check_if_number_is_new_prime = false
break
} else {
check_if_number_is_new_prime = true
}
}
return check_if_number_is_new_prime
}

func FindNewPrime() uint64 {
for counter := primes[len(primes)-1]; ; counter += 2 {
if CheckIfIsNewPrime(counter) == true {
return counter
}
}
return 0
}

func main() {
limit := 2000000
var sum uint64
sum = 5

for i := 2; i < limit; i++ {
primes = append(primes, FindNewPrime())
sum += primes[len(primes)-1]
}

fmt.Println("sum: ", sum)

}

-

Algorithm : really important

What you want to to is to use the Sieve of Eratosthenes because you already know an upper bound for the biggest number you're going to consider. Getting all the primes smaller than 2 millions is going to be straightforward. This will solve your process took too long issue.

Other things not as important

• You could probably write the following function :

func CheckIfIsNewPrime(number uint64) bool {
check_if_number_is_new_prime := false
var remainder uint64 = 0

for i := range primes {
remainder = number % primes[i]
if remainder == 0 {
check_if_number_is_new_prime = false
break
} else {
check_if_number_is_new_prime = true
}
}
return check_if_number_is_new_prime
}


in a more concise way (no real impact on performance)

func CheckIfIsNewPrime(number uint64) bool {
for i := range primes {
if number % primes[i] == 0 {
return false
}
}
return true
}

• I don't know anything about Go, but I guess

if CheckIfIsNewPrime(counter) == true {


could be written as

if CheckIfIsNewPrime(counter) {


As you go further in Project Euler, you'll see that most of the problem is to find the algorithm you want to use and not really to implement it.

-
Thanks for the hints Josay, I incorporated them (except for the else loop falling out). I see the Euler Problems more of a way to learn a new language (and prepare a bit for possible job interviews, where i would have to solve problems out of my head). I would have never come up with the Sieve algo, hence the implementation by trial division. I impoved the performace a bit by setting an upper bound as I dont have to check against division by all previous primes. I discovered a major misconception in my code: I tries to sum till the 2 millionth prime instead of all primes below 2 mio. –  Da Frenk Apr 2 '13 at 12:48
You're more than welcome. You'll really need to change the algorithm if you want to get any result (either for that problem or for a one later on). Also it's a classic algorithm which is always good to implement. –  Josay Apr 2 '13 at 14:22

Here's a full solution to the problem. I've given verbose comment in the code rather than give an explanation in prose.

func sumOfPrimes(lengthToSum int) int {

primes := []int{2}
// next to check = 1 + the last number in the primes list
// primeCounter := len(primes)

pPrime := primes[len(primes)-1] + 1
// if pPrime is even
if pPrime%2 == 0 {
// make pprime odd
pPrime += 1
}

for ; pPrime < lengthToSum; pPrime += 2 {
// iterate through each prime value in the known primes list
maxFactor := int(math.Sqrt(float64(pPrime))) // the larges possible factor for pPrime
// idx = 1, as we never need to check the first prime (i.e. 2)
for idx := 1; idx < len(primes); idx++ {
// if remaining primes are bigger than maximum possible factor size
if primes[idx] > maxFactor {
// pPrime must be a prime, so can end loop
break
}
if pPrime%primes[idx] == 0 {
goto newloop
}
}
// pPrime is a prime, so add to list of primes
primes = append(primes, pPrime)
newloop:
}
// sum the primes:
sum := 0
for i := 0; i < len(primes); i++ {
sum += primes[i]
}
return sum
}

-

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.