Thursday, January 19, 2012

Project Euler Problem 10 in Scala

This is 10 in a series. The previous post is at, Project Euler Problem 9 in Scala.


Problem 10 on project Euler is:

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

Problem 10 posed an interesting issue for me.  I came up with a solution I thought would work well right away, but I couldn't seem to get the correct answer.  After poring over my code and playing around, I finally found my issue - my isPrime function had an error in it, causing me to be off by 2.  


What is interesting about this scenario is that I've been using that same function for lots of different problems, but since the function was only broken for the number 2, it didn't matter in those.  If I had some sort of test that say, verified the function against a random set of prime numbers, I would have found the issue much sooner. This speaks to how important it is to test even seemingly working things whenever you can.    


Another by product of the issue is that I did a little more research on calculating prime numbers.  Wikipedia had a nice article about the  Sieve of Eratosthenes.  This gave me a much better understanding of how it works.  While I am not changing my code (yet) to use a sieve, it was certainly valuable to learn more about how its done.  


Well, I did manage to finish it, and here is my solution.  Enjoy:


object Problem10 {
  def main(args: Array[String]): Unit = {
    var holder : BigDecimal = new BigDecimal(new java.math.BigDecimal("0"));
    (2 to 1999999).filter{next => val prime = isPrime(next);if(prime){holder = holder + new java.math.BigDecimal(new Integer(next).toString())};prime}
    println(holder)
  }
  
  /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
  def isPrime(number: Long) : Boolean = {
    if(number == 2)
      return true
    if(number%2==0 || number % 3==0)
      return false;
    val sqrt:Int = Math ceil (Math sqrt number)  intValue;
    (true /: (3 to sqrt))((isPrime, next) => {
      if(number % next == 0) 
        return false 
      isPrime
    })
  }
}


Now that I've completed #10, I get a Euler award.  I have become a 'Decathlete' for finishing 10 problems in a row.  


And with that, I think I will finish blogging about my Euler solutions.  I still plan on working through the problems, but I think I've worn out my Euler solution posts and will move on to some other interesting topics.