euler 5

Euler5.scala

class Euler5 {
  def isPrime(num: Int) = {
    (2 until num).forall(num % _ != 0)
  }

  /**
   * 숫자 n의 unique한 소인수 집합
   * @param num
   * @param fractions
   * @return
   */
  def intFraction(num: Int, fractions: Set[Int] = Set()): Set[Int] = {
    for (i <- 2 to num) {
      if (num % i == 0) return intFraction(num / i, fractions + i)
    }
    fractions
  }

  /**
   * 1 ~ num 사이 수의 최소공배수
   * @param num
   * @return
   */
  def lcm(num: Int) = {
    var factors: List[Int] = List[Int]()
    for (i <- 2 to num) {
      i match {
        case x if isPrime(i) => factors = x :: factors //소수면 추가
        case _ => {
          val fractions = intFraction(i)
          if (fractions.size == 1) { //소수가 아니면서 소수의 제곱수라면 소수 한번 더 추가
            factors = intFraction(i).head :: factors
          }
        }
      }
    }
    (1 /: factors)(_ * _)
  }
}

object Euler5 extends App{
  //1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
  //그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

  println(new Euler5().lcm(10))
  println(new Euler5().lcm(20))
}