Project Euler Problem 3 in Scala

This is 3 in a series.  The previous post is at, Project Euler Problem 2 in Scala.


I've been busy again this fall, but now that I have a couple of days off over the holiday, I thought I'd play around with some more Scala.  It is pretty slow going learning the language at this pace, but the day job calls...


Problem 3 on the Euler site states:

The prime factors of 13195 are 5, 7, 13 and 29.  What is the largest prime factor of the number 600851475143 ?

For this solution, I reused the isPrime method from an earlier problem.  Essentially I end up looping through all the values up to the square root of the number and record the primes.  The largest prime is the last one.


Here's my first solution:

object Problem3 {
  val number : Long =  600851475143L;

  def main(args: Array[String]): Unit = {  
val sqrt = Math.sqrt(number);
    var largest = 0L;
var current : Long = 2L;
while(current < sqrt.toLong) {
 if(number % current == 0) {
 if(isPrime(current)) {
    largest = current;
 }
      }
 current = current + 1L;
} 
println("Largest " + largest);

  }

  
  *//**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   *//*
  def isPrime(number: Long) : Boolean = {
    var half = Math.sqrt(number) 
    var current = 2;
    while(current < half) {
      if(number % current == 0) {
        return false;
      }
      current = current+1;
    }
    return true;
  }
}


After looking at my first solution to this problem, you can see that I have mutable state AGAIN.  Something about my Object Oriented brain just can't seem to get into the stateless-state-of-mind.  This is interesting for another reason, though. Mutable state, in general, isn't a particularly good thing.  That is, if you can solve a programming problem without mutable state, it is better than the solution with mutable state.  It shouldn't matter if you are using OO languages or Functional ones.  It seems the industries years of OO teachings have led to we engineers sort of ignoring this fact.  I guess mutable state isn't as clear in an OO language if you have good Encapsulation in your code, but its still something we should be paying attention to.  Luckily, I was able to refactor my solution.  Here's a better version:


object Problem3 {
  val number : Long =  600851475143L;

  def main(args: Array[String]): Unit = {  
 println("Largest is " + largestPrime(2L, Math.sqrt(number), 2L));
  }
  
  @tailrec def largestPrime(initialPrime : Long, limit : Double, currentNumber : Long) : Long = {
    if(currentNumber >= limit.toLong) {
      initialPrime
    } else {
      if(isPrime(currentNumber) && number % currentNumber == 0) {
        largestPrime(currentNumber, limit,  currentNumber + 1);
      } else {
        largestPrime(initialPrime, limit,  currentNumber + 1);
      }
    }
  }
  
 /**
   * Brute force method.  Perhaps a better method 
   * can be implemented here?  
   */
 def isPrime(number: Long) : Boolean = {
    var root = Math sqrt number
    var current = 2;
    while(current < root) {
      if(number % current == 0) {
        return false;
      }
      current = current+1;
    }
    return true;
  }
}


Here we have a new solution where all our mutable state has been removed.  I start by declaring the number for which we are trying to find the largest prime.  It is declared as a val, though, so we are guaranteed that the value can't change.  This is different than any other language I've used, but it seems a handy facility.  Next, I call the recursive largestPrime method, which uses Tail recursion to iterate the list.  


Of course, I still think there is a better way to determine if a number is prime or not, but this method is pretty efficient the way it is.


That's my solution for now.  Stay tuned for Problem 4....