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