Project Euler: Problem 27

euler.scala

package euler.zerosum

package object Prime {

  def primes(to: Int): Stream[Int] = sieveInt(Number.from(2).takeWhile(_ <= to), Nil.toStream)

  /**
   * Int型エラトステネスの篩
   */
  private def sieveInt(numbers: Stream[Int], primes: Stream[Int]): Stream[Int] = {
    if (primes.nonEmpty && math.pow(primes.last, 2) > numbers.last) {
      primes #::: numbers
    } else {
      val h = numbers.head
      sieveInt(numbers.tail.filter(_ % h != 0), primes #::: h #:: Stream[Int]())
    }
  }
}

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

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

Euler0027.scala

package euler.zerosum

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

object Euler0027 {

  def main(args: Array[String]) {
    val a = (-999 to 999).toStream
    // bは素数
    val b = primes(1000)
    val coefficients = a.flatMap(as => b.map(bs => (as, bs)))

    val t =
      coefficients
      .map(cos => {
        (cos._1, cos._2, from(0).takeWhile(n => isPrime(f(n, cos._1, cos._2))).length)
      })
      .maxBy(_._3)

    println(t._1 * t._2)
  }

  private def f(n: Int, a: Int, b: Int): Int = {
    n * n + a * n + b
  }

  private def isPrime(n: Int): Boolean = {
    n > 0 && getDivisors(n).isEmpty
  }
}