Largest Prime Factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Solution

Before implementing anything, let’s think how finding the prime factors works. Let’s consider the number from the description, 13195. We can just try all the numbers until we hit a prime, then check if it’s divisible by this prime. Once we found a factor, we can just divide the original number by it.

So, the 13195 turns into 13195 / 5 = 2639.

Then 2639 / 7 = 377.

Then 377 / 13 = 29.

And finally 29 / 29 = 1.

In fact, we could check each result to see if it’s a prime, because if it is, then we know that we’ve found the biggest prime factor and can just return it.

But there are some reasons not to do that as well. Let’s take a look at a complete solution, without that final optimization:

import EulerHelper.naiveIsPrime

import scala.annotation.tailrec

object Euler003 extends EulerApp {
  override def execute(): Long = primeFactors(600851475143L).max

  @tailrec
  private def primeFactors(n: Long, i: Int = 2, primesFound: List[Int] = List.empty): List[Int] =
    if (n == 1) primesFound
    else if (n % i == 0 && naiveIsPrime(i)) primeFactors(n / i, i + 1, primesFound :+ i)
    else primeFactors(n, i + 1, primesFound)
}

The prime check is done in a naive way, by checking all the numbers. It’s not efficient, and in the process we’re checking multiple numbers over and over again, but it’s still blazing fast. Now, the reason why the final optimization was not done, because it would make the app run much slower: doing the same check on longs rather than integers, made the app run 5 times as long.

  extension (n: Int) {
    def naiveIsPrime: Boolean = n match {
      case n if n < 2 => false
      case _          => (2 to Math.sqrt(n.toDouble).toInt).forall(n % _ != 0)
    }
  }

In the end, it doesn’t make sense to overly optimize such a simple problem. Out solution solves it and is easy to understand, so let’s move on.