17 Jan 2009

Project Euler problem 3 using Scala

I've been looking at Euler problem number 3 for a while, and came up with the simplest solution I could imagine that works. So simple in fact, that the Scala experience was a bit disappointing, the same implementation could easily be done in Java, C, C#, Python, etc, etc. However, no real reason to complicate things unnecessary, so here's the code:


class Euler3 {

def maxFactor(number: Long, factor: Int): Int = {

if (factor >= number) factor
else if (number % factor == 0) maxFactor(number / factor, factor)
else maxFactor(number, factor + 1)
}
}
object Euler3 {

def main(args: Array[String]): Unit = {
println("maxFactor" + new Euler3().maxFactor(317584931803L, 2))
}
}


What it does is factorizing the given number by the natural numbers starting at 2. Whenever the number can be divided by the factor, the function is called recursively with the result of this division. If the number is cannot be divided by the factor, the factor is increased by one and again the function is called recursively. This continues until the factor and the resulting number are equal.
As a simple example, lets find the largest prime factor of 100.
First it is divided twice by 2, yielding 25. After this, it cannot be divided by 2 any longer, so the factor is increased to 3 and 4 (both not applicable) and eventually 5. Then 25 is divided by 5 exactly 5 times, yielding 5 as the resulting value.
Simple but effective.

No comments:

Post a Comment