Problem: Euler Task 3 - Largest Prime Factor

(Décidement, je suis en forme pour coder ce weekend. Après tout, avec le mauvais temps à Cote d'Azur ...)

Still from euler project. Now for task 3: largest prime factor. The integer factorization is an important subject and indeed it finds its application in cryptography. The fact that integer factorization is hard is used in many cryptography algorithms. But, to answer the question in euler project task 3, brute force approach should be enough since the integer to factorize is relatively small.

So, here we are. Here is the problem (http://projecteuler.net/index.php?section=problems&id=3)
"The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?"

First, the observation. The largest prime factor of 2 is 2. In general, I consider also that the largest prime factor of a prime number is the number itself. 

Then, we will try to check that the number is divided by a number. We check for every number from 2 until the square root of the checked number. Once found, the number is divided by the checked number and the result is again checked with the same algorithms, but with the checked number as the starting point (not 2). 

This yields the following implementation:

 1 
 2 import scala.collection.immutable.NumericRange
 3 
 4 def largestPrimeFactor(x: BigInt) = { 
 5   def largestPrimeFactor(x: BigInt, max: BigInt) : BigInt = {
 6      if (x == 2)  x 
 7      else {
 8         val nextFactor = 
 9           new NumericRange.Inclusive[BigInt](max, csqrt(x), 1).
10              find(x % _ == 0)
11         nextFactor match {
12           case Some(fct) => largestPrimeFactor( x / fct, fct)
13           case None => x
14         } 
15     }
16   }
17   largestPrimeFactor(x, 2)
18 }

Note the use of csqrt function that is  sqrt function implementation that works with BigInt. Then, line 8 - 10 is to get the first number that divides x. Line 11 - 13 acts accordingly, that is, if a factor is found, then it must be a prime number. Then x is divided by the found factor followed by recursive call to the same function.
If the find returns None, then it is the largest prime number.

As mentioned before, the brute force approach above is not practical for real problem with bigger number, especially for a number that is obtained by multiplying two large prime numbers. More sophisticated algorithms are required, and maybe I'll back to some of them one day in this blog. But for now, it's brute force.