Factorization with trial division (Scala)

From LiteratePrograms

This is a tiny program that factorizes integers between 2 and scala.Int.MaxValue, that is 2147483647. x is the number to factorize, y is the lowest number not tested yet.

The recursive fakt function matches x and y against a number of cases. In the base case, y has reached the same value as x:

<<Base case: x equal to y>>=
case (`y`, _)        => List(x)

If x ≠ y, then the case may be that y divides x evenly. If so, return a list consisting of y and the result of calling fakt on the quotient x/y and y. Since x/y will be less than x but not less than y, the recursion will eventually end.

<<x evenly divided by y>>=
case _ if x % y == 0 => y :: fakt(x / y, y)

If y is equal to 2, try again using the value 3 for y.

<<x not evenly divided by 2, try 3>>=
case (_, 2)          => fakt(x, 3)

If all else fails, try again using the next odd number (for further improvement, pick the next prime number instead).

<<x not evenly divided by y, try a bigger y>>=
case _               => fakt(x, y+2)

<<factorize.scala>>=
def fakt (x: Int, y: Int): List[Int] = (x, y) match {
  Base case: x equal to y
  x evenly divided by y
  x not evenly divided by 2, try 3
  x not evenly divided by y, try a bigger y
}
def factor (n: Int) = {
  require(n > 0)
  fakt(n, 2)
}
println(factor(120))
println(factor(scala.Int.MaxValue))

which we expect to produce:

List(2, 2, 2, 3, 5)
List(2147483647)

Download code