Recursive lazy impl of the Sieve of Eratosthenes, and using that to factor an arbitrary Int

primes.scala

import scala.annotation.tailrec

val primes: Stream[Long] = 2L #:: Stream.from(3, 2).map(_.toLong).filter(i => primes.takeWhile(j => j * j <= i).forall(k => i % k > 0))

def primesLTEQ(n: Long) = primes.takeWhile(_ <= n).map(_.toLong).toList

def primeFactors(n: Long): List[Long] = {

  @tailrec
  def loop(ps: List[Long], divs: List[Long], rem: Long): List[Long] = (rem, ps) match {
    case (n, _) if (n == 0) => List()
    case (n, _) if (n == 1) => divs
    case (n, _) if (n < 0) => loop(ps, divs :+ -1L, -1 * n)
    case (n, s) if (s.isEmpty) => divs :+ n
    case (n, h :: t) if (n % h == 0) => loop(ps, divs :+ h, n / h)
    case (n, h :: t) => loop(t, divs, n)
  }

  val primesToCheck = primesLTEQ(Math.sqrt(n.abs.toDouble).toLong)

  loop(primesToCheck, List(), n)

}

def primeFactorization(n: Long): Map[Long, Long] = primeFactors(n).groupBy(p => p).mapValues(_.size.toLong)

def phi(n: Long): Long = {
  def loop(acc: Long, ps: List[Long]): Long = ps match {
    case p1 :: p2 :: tail if p1 == p2 => loop(acc * p1, p2 :: tail)
    case p1 :: p2 :: tail if p1 != p2 => loop(acc * (p1 - 1), p2 :: tail)
    case pn :: Nil => acc * (pn - 1)
  }
  loop(1, primeFactors(n))
}