03.Scala で解く素因数分解　Scala基礎コース

# 目次

* 【講義】素因数分解のアルゴリズム
* 【実習】素因数分解を行うプログラムの実装方針を決める
* 【実習】素因数分解のアプリケーションのオブジェクトを作る
* 【講義】Scala でよく利用されるコレクション
* 【実習】再帰関数のインタフェースを定義する
* 【実習】再帰関数の中身の実装
* 【講義】再帰関数の中身の解説
* 【実習】素因数分解の動作を確認する

# 【講義】素因数分解のアルゴリズム

今回は、より高度な数学である素因数分解を Scala で解いてみよう。

素因数分解とは、与えられた数がどのような素数の掛け算によって表されるのか分かるよう、素数の積の形に分解する方法。

例えば 24 という数は、2 x 2 x 2 x 3 に分解できる。
つまり 2 が 3 つ、3 が 1 つに分けられる。

これをプログラムでやろうとした時に有名なアルゴリズムが存在する。
**試し割り法** という方法だ。

試し割り方法は、ある数が与えられたら、最小の素数である 2 から割れるかどうかをチェックしていく方法。
また、無事割り切れたならば再度その数で割っていく。

また割る数も最大で、最初に与えられた数の平方根の数までとなっている。
これは、その数の最大の約数がその数の平方根以上のものは、1 つしかないため。
例えば 9 の最大約数は 3 であるということを考えれば分かるだろう。

24 の例でやってみよう。

まず 2 で割る。
割り切れ、残る数が 12 となる。
2 で 1 回割り切れた。

12 を 2 で割る。
割り切れ、残る数が 6 となる。
2 で 2 回割り切れた。

6 を 2 で割る。
割り切れ、残る数が 3 となる。
2 で 3 回割り切れた。

3 を 2 で割る。
3 は割り切れないので、次の数である 3 で割る。

3 を 3 で割る。
割り切れ、残る数が 1 となる。
2 で 3 回、3 で 1 回割り切れた。

1 を 4 で割る。
1 は割り切れない。
また、24 の平方根は 4.89... なので、次の 5 では割ることはない。

最後に 1 が残っている。
これも因数の 1 つではあるが、素数ではないので結果には含めない。

よって答えは、2 で 3 回、3 で 1 回となる。

このようなアルゴリズムとなる。
ではこれをプログラムで実装してみよう。

# 【実習】素因数分解を行うプログラムの実装方針を決める

`scala-study` フォルダに `Factorization.scala` というファイルを作成しよう。
ここでは、24 の素因数分解をやってみよう。

```scala:Factorization.scala
object Factorization extends App {
  val target = 24

  println(target)
}
```

`Factorization` というオブジェクトを作成して、素因数分解の対象を target という変数に代入する。
そしてそのターゲットをコンソールに出力した。

sbt を `scala-study` フォルダで起動して、

```:Terminal
> runMain Factorization
```

を実行すると、

```:Terminal
24
[success] Total time: 4 s, completed 2021/07/26 9:38:38
```

以上のように表示されるダロウ。

ここから、24 を試し割り法で素因数分解する実装をしていく。
実装方針としては、以下のようになる。

1. 「対象」の平方根を計算してそれを「割る数の最大値」とする
1. 再帰関数として「対象」と、「割る数」と、現在の「結果」を受け取り、次の「結果」を返す関数を定義する
1. 関数の中身を定義する
1. 「割る数」が「割る数の最大値」よりも大きい場合、現在の結果に現在の「対象」を加えたものを答えとする
1. 「対象」が「割る数」で割り切れる場合、「結果」に「割る数」で割り切れた回数を 1 足して再度関数を実行する
1. 「対象」が割り切れない場合、「割る数」を 1 足して再度関数を実行する

関数の中身をフローチャートでかくと、以下のようになる。

なお、ここでは「対象」を num 、「割る数」を divisor 、「割る数の最大値」を maxDivisor 、「結果」を acc とする。

# 【実習】素因数分解のアプリケーションのオブジェクトを作る

```scala:Facorization.scala
import scala.math.sqrt

object Factorization extends App {
  val target = 24
  val maxDivisor = sqrt(target).toInt

  println(maxDivisor)
}
```

以上のように実装する。
これらを解説していく。

```scala
import scala.math.sqrt
```

これは平方根を求める関数 [def sqrt(x: Double): Double](https://www.scala-lang.org/files/archive/api/2.12.6/scala/math/index.html) を利用できるようにしている。

```scala
val maxDivisor = sqrt(target).toInt
```

以上で、 sqrt 関数を利用して「割る数の最大値」を計算している。
ただし、 sqrt 関数は戻り値の型が浮動小数点数である Double 値であるため toInt メソッドを呼ぶことで Int 型に変換している。
これで小数点部分は切り捨てられる。

そして最後に println 関数で「割る数の最大値」をコンソールに出力している。

まずはここまでで sbt で実行してみよう。

```:Terminal
> runMain Factorization
```

を実行すると、

```:Terminal
[info] running Factorization 
4
[success] Total time: 1 s, completed 2021/07/26 9:53:13
```

と 4 が表示されれば成功。
これでアプリケーションの土台が出来上がり、「割る数」 maxDivisor の最大値が計算できた。

# 【講義】Scala でよく利用されるコレクション

次に、素因数分解の結果を保持するために Scala でよく利用されるコレクションを紹介する。

* シーケンスを表す [Seq](https://www.scala-lang.org/files/archive/api/2.12.6/scala/collection/Seq.html)
* 連想配列を表す [Map](https://www.scala-lang.org/files/archive/api/2.12.6/scala/collection/Map.html)

以上2つの紹介をする。

まずは Seq 。
これはシーケンスという1つの種類の型から構成される要素のコレクション。
配列と同じように添字も利用できる。

内部的な実装は異なるが、使い方はほとんど配列と同じ。

REPL でちょっと動きを見てみよう。
`workspace` フォルダの `scala-study` にて、 `sbt console` を実行して REPL を立ち上げ、 `Seq(1,2,3)` を実行してみよう。

```scala:Terminal
scala> Seq(1,2,3)
res0: Seq[Int] = List(1, 2, 3)
```

`Seq(1,2,3)` は、 1 と 2 と 3 という3つの値が含まれるシーケンス。
型は `Seq[Int]` となり、 Int 型が含まれる Seq として表現される。

なお、実際の内部実装には、 List という型が利用されているため、 `List(1,2,3)` と表示される。
なお、この List については、今後詳細に説明する機会があるので、ここでは省略する。

また、 `res0(0)` のように添字でアクセスすると、

```scala:Terminal
scala> res0(0)
res1: Int = 1
```

以上のように添字の値が取得される。
配列と同じように添字は 0 始まりとなっている。
また Scala ではこのようなコレクションは基本的に不変のコレクションで、値を追加する際には、要素が追加された新しい Seq を作成する。

要素を増やす際には、

```scala:Terminal
cala> res0 :+ 4
res3: Seq[Int] = List(1, 2, 3, 4)
```

以上のように `:+` という演算子で 4 を要素に足した Seq を作成可能。
この `:+` は算術演算子のようにも見えるが、実は Seq が持つメソッド。

次に、 Map 。
おなじみの連想配列。
REPL で `Map("key1" -> 1, "key2" -> 2)` と入力して、連想配列を作ってみよう。

```scala:Terminal
scala> Map("key1" -> 1, "key2" -> 2)
res4: scala.collection.immutable.Map[String,Int] = Map(key1 -> 1, key2 -> 2)
```

以上のように表示される。
`scala.collection.immutable.Map[String, Int]` は実際の型が `scala.collection.immutable.Map` であり、キーの型が String 型、値の型が Int 型であることを表している。

次に `res4("key2")` のように入力してみよう。

```scala:Terminal
scala> res4("key2")
res6: Int = 2
```

キーを `()` で引数で与えると、その値が取得される。
また、この Map も基本的には不変のコレクション。
キーと値の組み合わせを追加したい場合には、 `res4 + ("key3" -> 3)` のように入力すると、

```scala:Terminal
scala> res4 + ("key3" -> 3)
res7: scala.collection.immutable.Map[String,Int] = Map(key1 -> 1, key2 -> 2, key3 -> 3)
```

以上のように、

```scala
Map(key1 -> 1, key2 -> 2, key3 -> 3)
```

というキーと値が新たに追加された連想配列が作成される。

ここまでで、 Seq と Map という2つの Scala のコレクションを学んだ。
今回の素因数分解の結果では、どちらのコレクションも使える。

今回は、表示された時に見やすい連想配列の Map を素因数分解の「結果」の型として利用してみよう。

# 【実習】再帰関数のインタフェースを定義する

ではまず、インターフェイスを実装してみよう。

```scala:ZFactorization.scala
import scala.math.sqrt

object Factorization extends App {
  val target = 24
  val maxDivisor = sqrt(target).toInt

  def factorizationRec(num: Int, divisor: Int, acc: Map[Int, Int]): Map[Int, Int] = {
    Map(2 -> 3, 3 -> 1)
  }

  println(factorizationRec(target, 2, Map()))
}
```

以上のように実装できる。
ここでは、素因数分解を行う再帰関数を定義する。

この素因数分解を行う関数は factorizationRec という名前とし、素因数分解の結果は Map で表される連想配列とした。

```scala
def factorizationRec(num: Int, divisor: Int, acc: Map[Int, Int]): Map[Int, Int]
```

以上の記述は関数名を factorizationRec とし、現在の数値である「割られる数」を Int 型の num 、「割る数」を Int 型の divisor 、ここまでの結果を Map[Int, Int] 型の acc としてキー、値ともに Int 型を持つ連想配列として定義した。
ちなみに acc とは、アキュムレーター (accumulator) の略で累算器という意味。
これまでの素因数分解の結果を累算して保持しているので、このように名付けられている。
戻り値も同様に、 Map[Int, Int] としてある。

そして、

```scala
Map(2 -> 3, 3 -> 1)
```

はあらかじめ答えとなる、 2 が 3 回、 3 が 1 回という素因数分解の結果を入力してある。

```scala
println(factorizationRec(target, 2, Map()))
```

は関数の呼び出しで対象となる数を target 、再帰を始める「割る数」 divisor の初期値を 2 、連想配列は空を表す `Map()` として呼び出してある。

では sbt で実行してみよう。

```:Terminal
> runMain Factorization
```

を実行すると、

```:Terminal
[info] running Factorization 
Map(2 -> 3, 3 -> 1)
[success] Total time: 4 s, completed 2021/07/26 14:57:43
```

と `Map(2 -> 3, 3 -> 1)` が表示されれば成功。

# 【実習】再帰関数の中身の実装

関数の中身は、以下のアルゴリズムを慎重に実装する。

1. 「割る数」が「割る数の最大値」よりも大きい場合、現在の結果に現在の「対象」を加えたものを答えとする
1. 「対象」が「割る数」で割り切れる場合、「結果」に「割る数」で割り切れた回数を 1 足して再度関数を実行する
1. 「対象」が割り切れない場合、「割る数」を 1 足して再度関数を実行する

以下のように実装できる。

```scala:Factorization.scala
import scala.math.sqrt

object Factorization extends App {
  val target = 24
  val maxDivisor = sqrt(target).toInt

  def factorizationRec(num: Int, divisor: Int, acc: Map[Int, Int]): Map[Int, Int] = {
    if (divisor > maxDivisor) {
      if (num == 1) acc else acc + (num -> 1)
    } else if (num % divisor == 0) {
      val nextAcc = acc + (divisor -> (acc.getOrElse(divisor, 0) + 1))
      factorizationRec(num / divisor, divisor, nextAcc)
    } else {
      factorizationRec(num, divisor + 1, acc)
    }
  }

  println(factorizationRec(target, 2, Map()))
}
```

とりあえず、手を動かして実装してみよう。

# 【実習】再帰関数の中身の解説

では、実装の説明をする。

```scala
    if (divisor > maxDivisor) {
      if (num == 1) acc else acc + (num -> 1)
```

ここでは、「割る数 (divisor) 」が「割る数の最大値 (maxDivisor) 」より大きくなってしまった時に、現在までの結果に今の「破られる数 (num) 」を足して答えにする。
ただし、「割られる数 (num) 」が 1 の場合は、 1 は約数にならないので足さず、そのままの結果を返す。

```scala
    } else if (num % divisor == 0) {
      val nextAcc = acc + (divisor -> (acc.getOrElse(divisor, 0) + 1))
      factorizationRec(num / divisor, divisor, nextAcc)
```

これは、『「割る数」 divisor で割り切れる』の実装。

```scala
val nextAcc = acc + (divisor -> (acc.getOrElse(divisor, 0) + 1))
```

現在の「結果」 acc をもとに、現在の「結果」のキーの答えが 1 多くなるような、 nextAcc という値を作っていく。

Scala では連想配列の Map に、

```
Map() + (key -> value)
```

以上の形式で記述することにより、そのキーの値を、 key と value で更新した新しい Map を取得できる。

ここでは、 divisor である「割る数」をキーに、 `acc.getOrElse(divisor, 0)` で得られる、現在の割った回数に 1 を足した値のものを取得している。

Map の getOrElse メソッドは、第一引数にはそのキーを与え、第二引数にキーの値がなかった場合の値を設定できる。
そのためここでは「割る数」 divisor に対して、値が設定されていなかった際には 0 が取得される。

```scala
factorizationRec(num / divisor, divisor, nextAcc)
```

この実装は、「割られる数」 num は既に割れた数、そして同じ「割る数」 divisor で結果を更新して、再帰呼び出しをしている。

```scala
    } else {
      factorizationRec(num, divisor + 1, acc)
```

こちらは割り切れなかった場合。
「割られる数」 num はそのまま「割る数」 divisor を 1 足して、「結果」 acc も同じものを利用して再起呼び出しを行う。

# 【実習】素因数分解の動作を確認する

ここまで実装できたら、 sbt で実行してみよう。

```:Terminal
> runMain Factorization
```

を実行すると、

```:Terminal
[info] running Factorization 
Map(2 -> 3, 3 -> 1)
[success] Total time: 1 s, completed 2021/07/26 15:13:58
```

と `Map(2 -> 3, 3 -> 1)` が表示されれば成功。
target の値を変えてみよう。

* 32 は、 Map(2 -> 5)
* 56 は、 Map(2 -> 3, 7 -> 1)
* 90 は、 Map(2 -> 1, 3 -> 2, 5 -> 1)
* 510510 は、 Map(5 -> 1, 13 -> 1, 2 -> 1, 17 -> 1, 7 -> 1, 3 -> 1, 11 -> 1)

それぞれを変更して、以上の正解になっているか確認しよう。
target を それぞれ、 32 , 25 , 90 , 510510 に更新して、

```:Terminal
> runMain Factorization
```

以上を実行する。
それぞれ正しい答えを導くことができたのではないだろうか。

このようにして、 Scala を使って素因数分解を行うプログラムを実装できる。

例えば、 510510 のような大きな数の素因数分解は、実際に手で行おうとすると非常に大変だが、プログラムにやらせると一瞬。

#  まとめ

* Scala には、シーケンスを表す Seq と連想配列を表す Map というコレクションがある
* Scala の Seq と Map は基本的には不変なコレクションで、それ自身を変更することはできない
* 不変のコレクションは、追加操作をすることで、追加された別のコレクションを取得できる

# 挑戦

## 初級

```scala:Factorization.scala
import scala.math.sqrt

object Factorization extends App {

  def factorization(target: Int): Map[Int, Int] = {
    val maxDivisor = sqrt(target).toInt

    def factorizationRec(num: Int, divisor: Int, acc: Map[Int, Int]): Map[Int, Int] = {
      if (divisor > maxDivisor) {
        if (num == 1) acc else acc + (num -> 1)
      } else if (num % divisor == 0) {
        val nextAcc = acc + (divisor -> (acc.getOrElse(divisor, 0) + 1))
        factorizationRec(num / divisor, divisor, nextAcc)
      } else {
        factorizationRec(num, divisor + 1, acc)
      }
    }

    factorizationRec(target, 2, Map())
  }

  println(factorization(510510))
}
```

```scala:sbt_console
scala> Factorization.factorization(24)
res1: Map[Int,Int] = Map(2 -> 3, 3 -> 1)
```

## 中級

```scala:PrintFactorization.scala
object PrintFactorization extends App {
  Seq(32, 25, 90, 510510).map(Factorization.factorization).map(println)
}
```

```scala:sbt
sbt:scala-study> runMain PrintFactorization
[info] running PrintFactorization 
Map(2 -> 5)
Map(5 -> 2)
Map(2 -> 1, 3 -> 2, 5 -> 1)
Map(5 -> 1, 13 -> 1, 2 -> 1, 17 -> 1, 7 -> 1, 3 -> 1, 11 -> 1)
[success] Total time: 1 s, completed 2021/07/26 16:52:37
```

## 上級

```scala:Euclid.scala
object Euclid extends App {
  def greatestCommonDivisor(a: Int, b: Int): Int = {
    if (a == 0) {
      b
    } else if (b == 0) {
      a
    } else {
      greatestCommonDivisor(b, a % b)
    }
  }
}
```

```scala:sbt_console
scala> Euclid.greatestCommonDivisor(36,24)
res0: Int = 12
```