Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

http://projecteuler.net/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)

}
share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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