S-99 P31-P35 My Work

gistfile1.scala

// *** S-99: Ninety-Nine Scala Problems ***
// http://aperiodic.net/phil/scala/s-99/
//
// wget http://www.scala-tools.org/repo-releases/org/scalatest/scalatest_2.9.0-1/1.6.1/scalatest_2.9.0-1-1.6.1.jar
// scala -cp scalatest*.jar s99-31-35.scala

import org.scalatest.matchers.ShouldMatchers._

class NotImplementedYet extends RuntimeException

// P31: Determine whether a given integer number is prime.
//      素数かどうかを判定する
object P31 {
  case class P31Int(i: Int) {
    def isPrime: Boolean = {
      if (i <= 1) false
      else ! ((2 until i) map { j => i % j == 0 }).contains(true)
      /*
      val primes = Stream.cons(2, Stream.from(3, 2) filter { _.isPrime })
      i > 1 && (primes takeWhile { _ <= math.sqrt(i) } forall { i % _ != 0 })
      */
    }
  }
  implicit def fromIntToP31Int(i: Int): P31Int = P31Int(i)

  def test {
    {
      1.isPrime should equal(false)
      2.isPrime should equal(true)
      3.isPrime should equal(true)
      4.isPrime should equal(false)
      5.isPrime should equal(true)
      6.isPrime should equal(false)
      7.isPrime should equal(true)
      8.isPrime should equal(false)
      9.isPrime should equal(false)
      10.isPrime should equal(false)
      11.isPrime should equal(true)
      12.isPrime should equal(false)
      13.isPrime should equal(true)
      14.isPrime should equal(false)
      15.isPrime should equal(false)
    }
  }
}

// P32: Determine the greatest common divisor of two positive integer numbers.
//      Use Euclid's algorithm.
//      ユークリッドの互除法を使って最大公約数を求める
object P32 {
  def gcd(m: Int, n: Int): Int = {
    if (n == 0) m else gcd(n, m % n)
  }

  def test {
    {
      gcd(36, 63) should equal(9)
      gcd(42, 21) should equal(21)
      gcd(13, 17) should equal(1)
    }
  }
}

// P33: Determine whether two positive integer numbers are coprime.
//      Two numbers are coprime if their greatest common divisor equals 1.
//      二つの正の整数が互いに素かを判定する
object P33 {
  case class P33Int(i: Int) {
    def isCoprimeTo(j: Int): Boolean = P32.gcd(i, j) == 1
  }
  implicit def fromIntToP33Int(i: Int): P33Int = P33Int(i)

  def test {
    {
      35.isCoprimeTo(64) should equal(true)
      9.isCoprimeTo(8) should equal(true)
      5.isCoprimeTo(5) should equal(false)
      12.isCoprimeTo(18) should equal(false)
      9.isCoprimeTo(33) should equal(false)
    }
  }
}

// P34: Calculate Euler's totient function phi(m).
//      Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r <= m) that are coprime to m.
//      オイラーのファイ関数（その数以下でその数と互いに素な数の個数を求める）
object P34 {
  case class P34Int(i: Int) {
    import P33._
    def totient: Int = (1 to i) filter { j => i.isCoprimeTo(j) } length
  }
  implicit def fromIntToP34Int(i: Int): P34Int = P34Int(i)

  def test {
    {
      10.totient should equal(4) // 1,3,7,9
      11.totient should equal(10) // 1,2,3,4,5,6,7,8,9,10
    }
  }
}

// P35: Determine the prime factors of a given positive integer.
//      Construct a flat list containing the prime factors in ascending order.
//      素因数分解する
object P35 {
  case class P35Int(i: Int) {
    def primeFactors: List[Int] = {
      def _pf(result: List[Int], j: Int): List[Int] = {
        if (j > 1) {
          (2 to j) foreach {
            case k if j % k == 0 => return _pf(k :: result, j / k)
            case _ =>
          }
        }
        result
      }
      _pf(Nil, i) reverse
      /*
      import P31._
      val primes = Stream.cons(2, Stream.from(3, 2) filter { _.isPrime })
      def primeFactorsR(n: Int, ps: Stream[Int]): List[Int] = {
        if (n.isPrime) List(n)
        else if (n % ps.head == 0) ps.head :: primeFactorsR(n / ps.head, ps)
        else primeFactorsR(n, ps.tail)
      }
      primeFactorsR(i, primes)
      */
    }
  }
  implicit def fromIntToP35Int(i: Int): P35Int = P35Int(i)

  def test {
    {
      11.primeFactors should equal(List(11))
      315.primeFactors should equal(List(3,3,5,7))
      120.primeFactors should equal(List(2,2,2,3,5))
      30030.primeFactors should equal(List(2,3,5,7,11,13))
    }
  }
}

P31.test
P32.test
P33.test
P34.test
P35.test

// vim: set ts=4 sw=4 et: