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)
}