[Swift] 割らないか? 108個目のブログを記念してSwiftで108の煩悩を素因数分解してみた

はじめに

CX事業本部の中安です。まいどです。

先日自身のブログ投稿数が大台の100を迎えさせていただいたのですが

今ブログは早くも108個目の投稿となります。

108・・・。

人間の煩悩の数ですね！

年末になると除夜の鐘でお祓いをすることで有名な「108の煩悩」ですが、 季節外れなこの時期に108個目の投稿を迎えたので、 お祓いの意味で何かブログが書けないかと考えました。

108・・・。

108・・・。

何も思いつきません・・・。

108・・・。

108・・・。

108は素数じゃないな・・・。

そんな頭の中でよく分からない問答が始まったときに腹を決めました。 「ちょっとSwiftで素数についてやってみよう」と。

108は素因数分解するとどうなるのか。 そんなことをプログラミングに起こして何の役に立つのか。

いや、どこかの中学生のひとりにでも刺さればよいだろう。

まぁ、そんな感じでちょっと始めてみましょう。

素数と素因数分解

数学が好きな方なら今でも親しんでいるでしょうし、そうでない方も懐かしく思える言葉「素数」と「素因数分解」。 ちょっとおさらいしていきましょう。

素数 prime number

「素数」とは自分自身と1のみでしか割ることができない自然数のことです。

たとえば3は1 × 3でしか作り出せません。また、5は1 × 5でしか作り出せません。 こういう数字が「素数」になります。

逆に4は1 × 4の他に2 × 2でも作り出せますし、また、6は1 × 6の他に2 × 3でも作り出すことができます。 これは「素数」ではありません。「非素数」や「合成数」といった言い方をします。

自然数であることから素数に0と負の整数は含みません。また、1も素数ではありません。 これも素数の特徴なので押さえておきます。

素因数 prime factor

「素因数」とは自然数の約数になる素数のことです。

たとえば20の素因数は何になるでしょうか。

20が答えになる掛け算としては 1 × 20 2 × 10 4 × 5 の3つが浮かぶと思います。 このうち20と10と4は2で割れるので素数ではありません。 それを割ってみると10と5と2になり、素数が5と2の２つになりました。 この時点で残る10が素数ではないので更に割ると素数の5になります。

つまり、1 × 20 = (1) × (5 × 2 × 2)ですし、2 × 10 = (2) × (5 × 2)ですし、4 × 5 = (2 × 2) × (5)と表せます。

このように登場人物が1と2と5だけになったところで、このうち1は素数ではありませんから、残った2と5が20の素因数ということになります。

素因数分解 prime factorization

「素因数分解」とはある数の素因数を求めて積算の形に表すことをいいます。

先程は20の素因数が2と5であることが分かりました。 そして、先程の掛け算(積算)の数字の順番を入れ替えていくと

• 1 × 20 = 2 × 2 × 5 (× 1)
• 2 × 10 = 2 × 2 × 5
• 4 × 5 = 2 × 2 × 5

まったく同じ2 × 2 × 5で表すことができます。 2が2つあるということは2の2乗ですから、これを式に表すと

[latex]20 = 2^2 × 5[/latex]

という風に表されます。これが20の素因数分解になります。

素数かどうかを調べる

ここからが本題。まずはSwiftを使って対象の数値が素数かどうかを判定していこうと思います。 ただ「素数判定法」というのはガッツリ数学的な話っぽいので、細かい話はここではしないです(というか、できないです)。 とりあえず trial division(試し割り法)という方法があるようなので、そちらを採用してみようかと思います。

試し割り法 trial division

Wikipediaを引用します。(一部省略・書き換えをしています)

試し割り法は最も面倒ではあるが、最も理解しやすい素数判定アルゴリズムである。基本的な考え方は、素因数分解しようとする整数nを小さい順に割ってみて、割り切れるかどうかを調べる手法である。

与えられた整数nに対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う。nが2で割り切れる確率は、nが3で割り切れる確率より高いため、小さい数から順に素因数の候補として割り切れるかを確かめると効率的である。また、nが2で割り切れない場合には4で割り切れないことは明らかであるため、4で割り切れるかを確かめる必要はない。同様に、既に確かめた数の倍数について確かめる必要はないため、素因数候補として確かめる数を素数のみとすることで、労力を削減できる。また、nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきはnの平方根までで十分ある。

いやー、文章がややこしいですね。少し噛み砕いてまとめてみましょう。

先程も例に出した20という数字は素数でしょうか？それとも合成数でしょうか？ 試し割り法の手法を使って調べてみましょう。

与えられた整数nに対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う

引用文に書かれているこの文を、算数でも出てくる「割り算と余り」の形に列挙するとこのようになりますね。 「与えられた整数n」とは20のことであり、20より小さい数で順番に割り算をしています。

20 ÷ 1 = 20 ... 0
20 ÷ 2 = 10 ... 0
20 ÷ 3 = 6 ... 2
20 ÷ 4 = 5 ... 0
20 ÷ 5 = 4 ... 0
20 ÷ 6 = 3 ... 2
20 ÷ 7 = 2 ... 6
20 ÷ 8 = 2 ... 4
20 ÷ 9 = 2 ... 2
20 ÷ 10 = 2 ... 0
20 ÷ 11 = 1 ... 9
20 ÷ 12 = 1 ... 8
20 ÷ 13 = 1 ... 7
20 ÷ 14 = 1 ... 6
20 ÷ 15 = 1 ... 5
20 ÷ 16 = 1 ... 4
20 ÷ 17 = 1 ... 3
20 ÷ 18 = 1 ... 2
20 ÷ 19 = 1 ... 1
20 ÷ 20 = 1 ... 0

余りが0になるもの全てが「割り切れる」ということです。

nが2で割り切れる確率は、nが3で割り切れる確率より高いため、小さい数から順に素因数の候補として割り切れるかを確かめる

何度も当たり前のことを書いてしまうのですが、整数nを1で割ると必ず割り切れます。 また、整数nを整数nで割っても必ず割り切れます。

したがって、整数nが素数だろうと合成数だろうと一番最初と一番最後の割り算は必要ありません。 なぜなら素数は「自分自身と1のみでしか割ることができない」数字のことですし、 合成数は「自分自身と1で割れるし、他の数字でも割れる」数字のことだからです。 「自分自身と1で割れる」ということは共通しているのです。

したがって確認は2から始まります。

小さい順から始める理由は「割り切れる確率が高いため」と書かれていますが、具体的には

与えられた範囲の整数に対して素数判定をする場合、2で割り切れる確率は50%であり、3で割り切れる確率は約33%であり、88%の自然数は100未満の約数を持つ、92%の自然数は1000未満の約数を持つ。

という理由になります。

既に確かめた数の倍数について確かめる必要はないため、素因数候補として確かめる数を素数のみとする

引用文で例示されているように「nが2で割り切れない場合には4で割り切れないことは明らかであるため、4で割り切れるかを確かめる必要はない」とのことです。 この原理でいくと「nが3で割り切れない場合には6で割り切れない」ですし「nが5で割り切れない場合には10で割り切れない」ことになります。 なので素数で確認するだけで事が足りると言っているわけですね。

さて、20より小さい素数はどれだけあるかというと

2、3、5、7、11、13、17、19 です。

先程20までのすべての数字で割ってみましたが、ここまでの話を元に間引いていくと

20 ÷ 2 = 10 ... 0
20 ÷ 3 = 6 ... 2
20 ÷ 5 = 4 ... 0
20 ÷ 7 = 2 ... 6
20 ÷ 9 = 2 ... 2
20 ÷ 11 = 1 ... 9
20 ÷ 13 = 1 ... 7
20 ÷ 17 = 1 ... 3
20 ÷ 19 = 1 ... 1

20個あった式が9個に減ることになります。

素因数候補として確かめるべきはnの平方根までで十分ある

素数と合成数に関係なく小さい順に割り算をしていたところまで話を戻します。 1で割っている式はスキップして、先程列挙した式を「20を求める逆算の式」に変換してみましょう。

20 = 2 × 10 + 0
20 = 3 × 6 + 2
20 = 4 × 5 + 0
20 = 5 × 4 + 0
20 = 6 × 3 + 2
20 = 7 × 2 + 6
:
:

掛け算をしている箇所を見てください。 ある位置から「かける数」と「かけられる数」の大きさが逆転しているところがあります。 3〜4行目の4 × 5と5 × 4のところです。

引用文には「nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである」とややこしく書かれていますが、要は「かける数」と「かけられる数」の大きさが逆転するときに素数判定する材料は出揃っているということです。

この逆転する位置はどうやって分かるのか？というと、逆転する位置は「整数nの平方根になる」という法則があります。

ルート20は約4.47になるのですが、ここを境に「かける数」と「かけられる数」が逆転するので、 試すべき上限は4までで十分というわけです。

ここまでのまとめ

ここまでの「素数で確認するだけで事が足りる」と「整数nの平方根までを確認するだけで事が足りる」という2つを組み合わせると

20 ÷ 2 = 10 ... 0
20 ÷ 3 = 6 ... 2

9個あった式が２個の式までに減りました。

もう一度念のために書きますと、素数は「自分自身と1のみでしか割ることができない」数字です。 しかし、2で割ると割り切れるので「20は素数ではない」という結論に至ります。

20は偶数なので見た瞬間に「素数ではない」と分かるとは思いますが、機械的に判定するときにはこのような手順を踏むことになるというわけですね。

素数の場合はどうなるのか

23を例に出します。結論からいうと自然数23は素数です。 では、ここまでの方法で素数であるかどうかを調べて確認します。

23を小さい数字から順に割ったとして、その逆算はこちらです。

23 = 1 × 23 + 0
23 = 2 × 11 + 1
23 = 3 × 7 + 2
23 = 4 × 5 + 3
23 = 5 × 4 + 3
23 = 6 × 3 + 5
:
:
23 = 22 × 1 + 1
23 = 23 × 1 + 0

そして

• 1と自身(23)の割り算(逆算時は掛け算)は不要
• 素数に絞る
• 23の平方根(ルート23 = 約4.79)まで

で絞ると

23 ÷ 2 = 11 ... 1
23 ÷ 3 = 7 ... 2

この2つの式から判定できます。 23では絞られた式に0が余るパターンは存在しないので「23は素数である」と結論付けられます。

素数を調べるために

ここまでの話で「素数を判定するためには割る数を素数に絞って確認する」ということがわかったわけですが、 よく考えると、そもそも素数に絞るための材料がないのではないでしょうか。

素数はいわば無限に存在します。 プログラミングで割る数を素数に絞るというのは難しいものと思います。

では、どうするかというと 素数に絞ることを諦めながらも計算回数が伸びない方法に倒すことになります。

2の扱い

まず2という素数の扱いです。 2自体は素数ですが、2の倍数はすべて合成数です。 そして2の倍数とはつまり「偶数」です。 つまり「2を除くすべての偶数は素数ではない」ということが言えます。

奇数の扱い

そして「奇数」の扱いです。 「2を除くすべての偶数は素数ではない」ですが、しかし当然ながら「すべての奇数が素数である」わけではありません。

ただし「この奇数は素数で、この奇数は素数ではない」と判定しながら進めることはできないので、 「2を含む3以降の奇数すべてで絞る」という方法を採ることになります。

範囲を絞る

「2を含む3以降の奇数すべてで絞る」と書きましたが、範囲は無限ではありません。

前項で書いたとおり、判定に使用する数字の上限は「整数nの平方根までで事足りる」という法則がありましたので、 言い換えると「2を含む整数nの平方根までの奇数すべてで絞る」ということになります。

巨大な数字でなければ範囲はかなり絞られると思います。

Swiftに落とし込む

前段がかなり長くなりました。 これだけ細かく書いたのはプログラミングに落とし込んだ時にその要件を分かりやすくするためです。

あらためてまとめてみましょう。

・「素数」とは自分自身と1のみでしか割ることができない自然数のこと

• 1と自分自身で割ってみる必要はない。
• 自分自身と1以外の数字で割り切れた時点で素数ではないと判定できる。
• 1より少ない数字は素数ではない。

・2以外の偶数は素数ではない

• 2を試してみた以降は、奇数だけで試すことになる。

・ある整数が素数かどうかを調べたい時、その整数の平方根までの素数を使って調べる

• 平方根を算出し、その数字までを順番に試すだけでいい。

プログラムの要件が見えましたね。

書いてみる

Intのextensionを作って、以下のような計算プロパティを定義することにします。

extension Int {
    
    /// 素数かどうか
    var isPrimeNumber: Bool {
        
        // 1以下は素数ではない
        if self <= 1 { return false }
        
        // 2は素数
        if self == 2 { return true }
        
        // 偶数は素数ではない
        if self % 2 == 0 { return false }
        
        // 平方根を計算(整数化する)
        let squareRoot = Int(sqrt(Double(self)))
        
        // 平方根までの奇数で順番に割ってみる
        for i in stride(from: 3, through: squareRoot, by: 2) {
            if self % i == 0 {
                return false
            }
        }
        
        // 割り切れなかった場合は素数
        return true
    }
}

このうち最初の3行で数字の範囲を絞っています。

if self <= 1 { return false }
if self == 2 { return true }
if self % 2 == 0 { return false }

「1より少ない数字は素数ではない」「2は素数である」「2以外の偶数は素数ではない」という条件がこの分岐で絞れます。 そうするとここを通過できるのは3以上の奇数ですね。

ここで平方根が出てくることになります。平方根を求めるためにはsqrt()関数を使用します。 sqrt()関数はDouble型を引数にしてDouble型で返しますが、 Intにキャストすることで小数点以下を切り捨てます。

let squareRoot = Int(sqrt(Double(self)))

stride()関数を使うと、刻み方を指定してループできます。 3から2ずつ刻むことで確実に奇数のみでループし、無駄な偶数の計算はさせないようにします。

for i in stride(from: 3, through: squareRoot, by: 2)

stride()関数にはstride(from:through:)とstride(from:to:)の2種類があります。 to:の場合は与えた値を含まないのに対して、through:の場合はその値を含みます。

49 = 7 × 7で平方数で割れるため素数ではないのですが、49の平方根は7であるため、 stride(from:to:)を使うとこの計算が狂ってしまいます。

あとは、割り切れる数があった時点で合成数。最後まで割り切れる数がなかったら素数という判定になります。

if self % i == 0 {
    return false
}

素数を一覧化する

isPrimeNumberを作ったので、指定した範囲の素数をすべて配列で返す静的なメソッドも作ることができます。

extension Int {
    
    /// 素数かどうか
    var isPrimeNumber: Bool { get }
    
    /// 指定した範囲の素数をすべて配列で返す
    static func primeNumbers(max: Int, min: Int = 2) -> [Int] {
        if max < min { return [] }
        
        return (min...max).reduce(into: [Int]()) { res, i in
            if i.isPrimeNumber {
                res.append(i)
            }
        }
    }
}

試しに100までの素数を出してみましょう。

let primes = Int.primeNumbers(max: 100)

// [2, 3, 5, 7, 11, 13, 17, 19, 
//  23, 29, 31, 37, 41, 43, 47, 
//  53, 59, 61, 67, 71, 73, 79, 
//  83, 89, 97]

素因数分解をする

実際に素因数分解をするプログラムを書いてみます。

そういえば、素因数分解ってどうやるんでしたっけ？ なんかこういう筆算をやりましたよね。

小さな素数から割れるところまで割って、最後に1になったら終わり・・・という筆算です。 複数か言われる場合は指数を使って、まとめるのが決まりですね。

となると、最終的には使用する素数と指数が欲しいので、タプル化して返すようなメソッドを作ってみます。

extension Int {
    
    /// 素数かどうか
    var isPrimeNumber: Bool { get }
    
    /// 指定した範囲の素数をすべて配列で返す
    static func primeNumbers(max: Int, min: Int = 2) -> [Int] { get }
    
    /// 素因数分解する
    func primeFactorization() -> [(prime: Int, count: Int)]? {
        // 1以下はnil
        if self <= 1 { return nil }
        
        var ret: [(prime: Int, count: Int)] = []
        var divided = self
        var count = 0
        let primes = Int.primeNumbers(max: self)
        
        for prime in primes {
            if divided % prime == 0 {
                count = 0
                repeat {
                    count += 1
                    divided = divided / prime
                } while divided % prime == 0
                
                ret.append((prime: prime, count: count))
            }
            if divided == 1 {
                break
            }
        }
        return ret
    }
}

1以下は素因数分解できないと思うので、nilを返す設計にしています。 あとは、上の筆算でやってることをループを使ってやっている感じです。

最終的には「素数と指数のタプル」(prime: Int, count: Int)の配列の形で返されるようにしました。 ここまで返ってくると、あとは煮るなり焼くなりできると思います。

さて 108 は・・・?

ここまでできると、いよいよ108を素因数分解することができます。

print(108.primeFactorization()!)

//[
//  (prime: 2, count: 2), 
//  (prime: 3, count: 3)
//]

つまり

[latex]108 = 2^2 × 3^3[/latex]

ですね

最後に

108を素因数分解しても人間の煩悩なんてお祓いされるわけがなかったのでした。

では、またー。