Fermat’s factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares. See more in Wikipedia.

#!/bin/sh exec scala "$0" "$@" !# def decomposeInPrimes(t: Int): Set[Int] = { var factors = Set[Int]() def isqrt(number: Float): Int = { val squareroot:Int = Math.sqrt(number).toInt squareroot } def fermat(n: Int) { var number = n while(number % 2 == 0) { number /= 2 factors += 2 } if (number == 1) { return } var r = isqrt(number) var is_prime = true while (r < (number + 1) / 2) { val m = ((r * r) - number).toFloat if (m >= 0 && Math.sqrt(m) == Math.floor(Math.sqrt(m))) { val s = isqrt(m) fermat(r - s) fermat(r + s) is_prime = false return } r += 1 } if (is_prime == true) { factors += number } } fermat(t) factors } val test = args(0).toInt println(decomposeInPrimes(test)) |

To run this program as script, save as “fermat.sh” and execute:

./fermat.sh 9941 |