Project Euler: Problem 35

euler.scala

package object Prime {

  def primes(from: Int, to: Int): Stream[Int] = Number
                                                .from(from)
                                                .takeWhile(_ <= to - from + 1)
                                                .filter(n => n != 1 && Divisors
                                                                       .getDivisors(n)
                                                                       .filterNot(_ == 1)
                                                                       .isEmpty)
}

package object Divisors {
  /**
   * 自身を除くnの約数を返す。
   * 約数は昇順にソートされる。
   *
   * @param n
   * @return
   */
  def getDivisors(n: Int): Stream[Int] = {
    val divs = Number.from(1).take(math.sqrt(n).toInt).filter(n % _ == 0)
    (divs ++ divs.map(n / _).filterNot(divs.contains(_))).filterNot(_ == n).sortWith(_ < _)
  }
}

package object Number {
  /**
   * n以上の整数の無限数列を生成する
   *
   * @param n
   * @return
   */
  def from(n: Int): Stream[Int] = n #:: from(n + 1)

  def everyTwoFrom(n: Int): Stream[Int] = n #:: from(n + 2)
}

Euler0035.scala

package euler.zerosum

import euler.zerosum.Prime._
import euler.zerosum.Divisors._

object Euler0035 {

  def main(args: Array[String]) {
    println(provideCircularPrimes(primes(1, 1000000), Nil).length)
  }

  private def provideCircularPrimes(primes: Stream[Int], circulars: List[Int]): List[Int] = {
    if (primes.isEmpty) {
      circulars
    } else {
      val cn = provideCircularNums(primes.head.toString, Nil)
      if (cn.forall(n => n.head != '0' && isPrime(n.toInt))) {
        provideCircularPrimes(primes.filterNot(p => cn.contains(p.toString)), cn.map(_.toInt) ::: circulars)
      } else {
        provideCircularPrimes(primes.tail, circulars)
      }
    }
  }

  private def isPrime(n: Int) = n != 1 && getDivisors(n).filterNot(_ == 1).isEmpty

  private def provideCircularNums(n: String, circulars: List[String]): List[String] = {
    if (circulars.contains(n)) {
      circulars
    } else {
      val l = n.toString.toList
      provideCircularNums((l.tail ::: l.head :: Nil).mkString, n :: circulars)
    }
  }
}