皆さんこんにちは！タカモリです。 今日もプログラミングをしながら楽しく数学を勉強していきましょう！

「整数の性質」ということで今日は素因数分解です。

素因数分解

皆さん覚えていますか？素因数分解！僕の記憶ではかなり遠くにあったので正直名前くらいしか覚えていませんでした！笑

素数はたまに聞いたりしますが、素因数分解という単語なんて最後にいつ聞いたか記憶にありませんね。。 ということでこの記事を見て「あぁせやせや！そんなんあったな！」となったあなたはラッキーです✨

特にこれを覚えてどうこうというわけではないのですが、数学を初心に振り返って勉強するという機会はあまりありませんよね。

というわけでまずは、素因数分解とはなんなのかということですが、この素因数という言葉には「素数」「因数」「素因数」という言葉が含まれています。 一つ一つ見ていきましょう。

素数とは

素数とは英語ではPrimeNumberというらしいですね。

正しくは「正の約数が1とその数自身である約数で、1でない自然数のことをいいます。」 ということらしいですが・・・ 分かりにくい笑

簡単にいうと、「1」と「その数自身」でしか割りきれない数を指すと覚えておけば良いのではないでしょうか？

ちなみに1から20までの素数は2 3 5 7 11 13 17 19となり以降続きます。

因数とは

因数という言葉！これなんかも完全に頭から消えてます笑 あの悪名だかき因数分解なら死ぬまで覚えていそうですが、因数単体だと？？という感じです。

調べてみると「一つの数や整式が、いくつかの数や整式の積の形で表されるときの、その個々の数や整式のこと。因子」のことらしいです。

つまり、80という数字を8×10とした場合のこの8と10のことを因数というみたいですね。

素因数とは

では素因数とは一体なんなのか。 調べると「素数の因数。整数を素数の積の形に書き表わしたときの各素数をその整数の素因数という。素約数。」とあります。

つまり上であげた因数のうち素数となるものと言い換えることができそうです。 80の場合は2×2×2×5と因数を素数とした場合2 2 2 5それぞれのことを素因数というようです。

この80を2×2×2×5と分けることを素因数分解と言います。

ではこれをプログラミングで記述していきましょう。

pythonで素因数分解してみた

素因数分解のアルゴリズムを考える前に、まずは日本語でロジックを考えてみます。しかし！結構というかかなり難しい笑。 80を2×2×2×5とするってどうすりゃいいんや！

まずは素数を判定するアルゴリズムを調べてみました。

素数の判定アルゴリズム

素数を判定するためには

まずは素数が素数かどうかを調べるロジックを考えてみました。 これを調べるためには例えば素数が7の場合、1と7以外で割り切れなければ良いので、2から6までの間順番に7÷3 7÷4 7÷5 7÷6とし、途中で割り切れた時点で素数ではないと判断すれば良いのかな？

kazu = 7
sosuu = True
for i in range(2, kazu):
　if kazu % i == 0:
    　sosuu = False
        break

ログに出してみるとこのように全ての数で割り切れていないことがわかるので

これで素数判定はできているような。ちなみに今回はルートをその数まで回していますが、実際にはその数の平方根を切り上げた数までで良いようです。(理由は絶対に俺に聞くなよ！)

素因数分解のアルゴリズム

これはね。かなり調べたのですが。正直かなり迷いました。 素因数分解のアルゴリズムはかなり効率を考えられたアルゴリズムも存在したのですが、とりあえず今回はこの形に落ち着きました。 いや、落ち着かせてください！笑

def soinsuubunkai(num):
　soinsuu = []
　for i in range(2, math.ceil(math.sqrt(num))):
　while (num % i) == 0:
　　soinsuu.append(i)
        num //= i
　return soinsuu

割る数iを素因数分解する数numのルート2を切り上げた数になるまで順番にnumを割っていきます。なお、あまりが0の時にその数を素因数として保存していきます。

ログを見てみると、これで素因数分解できているようです。個人の感想としては、一個一個のiに対して素因数かどうかを判定しなくて良いのか？とかなり疑問に感じているのですが、これで素因数分解になるようです。 皆さんスッキリします？・・・あれ？僕だけかな笑

あまり数学的なロジックを考えたことがなかったので今回はかなり勉強になりました。まだスッキリしていない部分もありますが、少しづつ数学とお友達になりたいと思います！