# Factorization with trial division (Scala)

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 xy, 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)
```