problem31-35

Mar 15, 2017 | 99-problems-in-scala

声明
该系列文章来自：http://aperiodic.net/phil/scala/s-99/
大部分内容和原文相同,加入了部分自己的代码。
如有侵权，请及时联系本人。本人将立即删除相关内容。

在接下来的章节，我们将采取不同的策略。声明了一个类-S99Int,和一个隐式转化器，用来从传统的Int转换到S99Int.

下面是该类的最初声明：

package arithmetic {
  class S99Int(val start: Int) {
    import S99Int._
  }
  object S99Int {
    implicit def int2S99Int(i: Int): S99Int = new S99Int(i)
  }
}

并且在每个问题中将给该类添加相关的功能。最终将得到一个完整的S99Int类。

P31 (**) Determine whether a given integer number is prime.

要求

Example:

1 2	scala> 7.isPrime res0: Boolean = true

代码

class S99Int(val start: Int) {
    import S99Int._
    def isPrime: Boolean =
        (start > 1) && (primes.takeWhile(_ <= Math.sqrt(start)).forall(start % _ != 0))
}
object S99Int {
    implicit def int2S99Int(i: Int): S99Int = new S99Int(i)
    val primes = Stream.cons(2, Stream.from(3, 2) filter { _.isPrime })
}

P32 (**) Determine the greatest common divisor of two positive integer numbers.

要求

Use Euclid’s algorithm.

1 2	scala> gcd(36, 63) res0: Int = 9

代码

1
2
3

object S99Int {
    def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(n, m % n)
}

P33 (*) Determine whether two positive integer numbers are coprime.

要求

Two numbers are coprime if their greatest common divisor equals 1.

1 2	scala> 35.isCoprimeTo(64) res0: Boolean = true

代码

class S99Int(val start: Int) {
    import S99Int._
    def isCoprimeTo(x: Int): Boolean = gcd(start, x) == 1
}

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.

1 2	scala> 10.totient res0: Int = 4

代码

class S99Int(val start: Int) {
    import S99Int._
    def totient: Int = (1 to start).filter(start.isCoprimeTo(_)).length
}

P35 (**) Determine the prime factors of a given positive integer.

要求

Construct a flat list containing the prime factors in ascending order.

1 2	scala> 315.primeFactors res0: List[Int] = List(3, 3, 5, 7)

代码

class S99Int(val start: Int) {
    import S99Int._
    def primeFactors: List[Int] = {
        def primeFactorsR(x: Int, ps: Stream[Int]): List[Int] = {
            x match {
                //本身就是素数
                case n if n.isPrime          => List(n)
                //能分解为n*ps.head
                case n if (n % ps.head) == 0 => ps.head :: primeFactorsR(n / ps.head, ps)
                //其他
                case n                       => primeFactorsR(n, ps.tail)
            }
        }
        return primeFactorsR(start, primes)
    }
}

scala