Problem Definition

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

What is the largest prime factor of the number 600851475143?

Source: https://projecteuler.net/problem=3

Solution

object Euler03 {

  type Factor = Long
  type Number = Long
  type Factors = List[Factor]

  /* Returns the largest prime factor of the given
   * number.It first computes all the prime factors of the given
   * number and then returns the largest among them.
   */
  def largestPrimeFactor (x: Number): Factor = 
    primeFactors(x).max


  /* Returns the prime factors of the given number x. For instance
   * if the number x equals to 5, it returns List(2,3).
   */
  def primeFactors(x: Number): Factors = {
    val numUpToSqrt = (2L to math.sqrt(x).toLong)
    val divisibleBy = numUpToSqrt.find(x % _ == 0)

    divisibleBy match {
      case None =>  List(x) 
      // x is a prime number and not divisible by any
      case Some(d) => d :: primeFactors(x/d)
    }
  }
}