# Project Euler 10: Summation of primes in Go

Here is my first try at googles Go language, trying to solve Eulers Problem 10:

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

One more thing, could somebody run this code on his machine and send me the result? Googles sandbox takes to long [process took too long]  to actually give me the result :).

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)

}


EDIT: Improved code that runs in googles sandbox

package main

import "fmt"

var primes = []uint64{2, 3}

func CheckIfNewPrime(number uint64) bool {
check_if_number_is_new_prime := false
upper_bound := primes[len(primes)-1]

for i := 0; primes[i] < upper_bound; i++ {
if number%primes[i] == 0 {
check_if_number_is_new_prime = false
break
} else {
check_if_number_is_new_prime = true
upper_bound = number / primes[i]
}
}
return check_if_number_is_new_prime
}

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

func main() {
var limit uint64
limit = 2000000
var sum uint64
sum = 2

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

}
fmt.Println(len(primes), "th prime: ", 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 straight forward. 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 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