Thursday, January 5, 2012

Project Euler Problem 7 in Scala

This is 7 in a series.  The previous post is at, Project Euler Problem 6 in Scala.


After a very successful solution to problem 6, we get to problem 7.  I couldn't figure out how to remove all mutable state from this solution.  The issue is that we have to find the 10,001st number which means that we do not know how long we have to iterate.  I used a while loop here, and it seems to work fine.  Perhaps someone has a solution without a while loop?  


Here's Project Euler problem 7:

 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
 What is the 10,001st prime number?

object Problem7 {


  def main(args: Array[String]): Unit = {
var counter = 1L;
var number = new BigDecimal(new java.math.BigDecimal("0"));
var currentNum = 1l;

while(counter <= 10001) {
 if(isPrime(currentNum)) {
   number = new BigDecimal(new java.math.BigDecimal(currentNum));
   counter = counter + 1;
 }
 currentNum = currentNum + 1;
}
println("10001st prime " + number);
  }
    
  /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
  def isPrime(number: Long) : Boolean = {
    if(number%2==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
    })
  }
} 


You should note that I've cleaned up my isPrime method.  I noticed that it wasn't very functionally written, so I changed it to use a fold left (By the way, foldLeft is turning out to be one of the handiest Scala constructs on the planet.)  I am now very comfortable with the isPrime method, at least as a brute force solution.