src/main/scala/prime_factors.scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
case class PrimeFactors() {
  // Counter stream for Longs
  private def countFrom(i: Long): Stream[Long] = i #:: countFrom(i + 1)
  // Find the lowest prime factor of n
  private def lowestPrimeFactor(n: Long) = countFrom(2) find { n % _ == 0 }

  def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
    case Some((a, b)) => a :: unfoldRight(b)(f)
    case None => Nil
  }

  def primeFactors(n: Long) = unfoldRight(n) {
    x =>
      if (x == 1) None
      else {
        val primeFactor = lowestPrimeFactor(x).get
        Some((primeFactor, x / primeFactor))
      }
  }
}

@abo64 thinks this looks great

Comments


You're not logged in right now. Please login via GitHub to comment