Skip to content

Instantly share code, notes, and snippets.

@andreisavu
Created March 8, 2011 22:16
Show Gist options
  • Save andreisavu/861206 to your computer and use it in GitHub Desktop.
Save andreisavu/861206 to your computer and use it in GitHub Desktop.
Find prime factors for an integer
import scala.math.{ceil,sqrt}
object Main {
def isPrime(n: Int): Boolean =
if (n <= 2) (n == 2) else {
val limit = ceil(sqrt(n)).toInt
def _check(i: Int): Boolean =
if (i > limit) true
else if (n % i == 0) false
else _check(i + 1)
_check(2)
}
def nextPrime(p: Int):Int =
if (isPrime(p + 1)) (p + 1) else nextPrime(p + 1)
def divide(x: Int, f:Int):(Int, Int) = {
def _divide(x: Int, c: Int):(Int, Int) =
if (x % f != 0) (x, c) else _divide(x / f, c + 1)
_divide(x, 0)
}
def factors(n: Int):List[(Int,Int)] = {
def _factors(x: Int, p: Int):List[(Int, Int)] = {
if (x <= 1) Nil else if (isPrime(x)) (x,1) :: Nil
else {
val (r, c) = divide(x, p)
if (c != 0) (p, c) :: _factors(r, nextPrime(p))
else _factors(r, nextPrime(p))
}
}
_factors(n, 2)
}
def main(args: Array[String]) {
println(factors(1999978910))
// List((2,1), (5,1), (29,1), (6896479,1))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment