# 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_ifx % 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>>=deffakt(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}deffactor(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 |