# 34: F# で素因数分解（Exercism）

Exercism F#

前回の投稿からしばらく間が空いてしまいましたが、再びプログラミングのことについて書いていこうと思います。ログを残しておけば結果的に自分にとって役に立ちますからね。

最近 Exercism というプログラミング学習サービスを利用し始めました。メジャーなものからマイナーなもの（Emacs Lisp とか！）まで、現時点で 55 のプログラミング言語のコース（track）があり、充実しています。

様々なお題（exercise）があり、順番に解いていくことでその言語の文法やイディオムを学べるようになっている、日本でいう Progate のような感じですね。

特徴としては、

  • 独自の CLI ツールがあり、ローカル環境で Exercise のコードならびにテストコードをダウンロードしてきて、編集して、投稿することができる。
  • 自分の解答を投稿したあとは他者の解答を参照することができる。
  • メンター制度があり、その言語について詳しい人からアドバイスを受けることができる。

というものがあります。

ひとまず今は F# track をやっています。

やったこと（Done）

素因数分解の exercise をやっていました。

与えられた数（int64）を素因数分解した結果を配列で返すというもの。

素数かどうか

まず素数かどうかを判定する関数 isPrime を書きます。

open System

// 素数かどうか判定する
let isPrime num =
    let sqrt (n: int64) = float n |> Math.Sqrt |> int64

    match num with
    | 0L
    | 1L -> false
    | 2L -> true
    | n -> List.forall (fun x -> n % x <> 0L) [ 2L .. (sqrt n) ]

素数とは「1 とその数自身以外では割り切れない正の整数」だと思いますので、[ n .. m] の記法で list を作って全てにおいて割り切れない（剰余が 0 ではない）ことを確認する、という処理です。

パターンマッチで 0, 1, 2 はベタ書きして、3 以上について一般化して書きました。

n 以下の素数を列挙

// n 以下の素数のリストを得る
let primeNumbers number = [ 0L .. number ] |> List.filter isPrime

List.filter を使うだけ。

素因数分解の結果をリストとして得る

// 素因数分解の結果をリストで返す
let factors (number: int64) =
    let results = []
    let primes = primeNumbers number

    let rec devider num (devisor: int64) (results: int list) =
        // 割られる数 num が割る数 devisor で割り切れたら
        if num % devisor = 0L then
            // その割る数 devisor を results に加える
            let newResults = (int devisor) :: results
            // さらに同じ数で割ってみる
            devider (num / devisor) devisor newResults
        else
            List.sort results

    List.fold (fun lst x -> devider number x lst) results primes

一見これでよさそうだと思ったのですが、テストの最後でめちゃくちゃ大きい数が渡されるものがあって、それがエラーになってしまいます。

わかったこと（Fact）

C# だと LINQ で Any() というメソッドがありますが、それと同様のものがあるか探したところ、逆のロジックのものがありました。

list の全てに対して評価式が true を返すかどうかをチェックする List.forall です。

> List.forall;;
val it : (('a -> bool) -> 'a list -> bool)

The predicate is applied to the elements of the input list. If any application returns false then the overall result is false and no further elements are tested. Otherwise, true is returned.

途中で false を返すものがあったらそれ以降の要素は走査しない、ということなので効率もよさそうです。