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

Advertisements