素因数分解

問題

$(1)\quad$ $100$以下の素数をすべて求めよ。

$(2)\quad$ $360$を素因数分解せよ。

$(3)\quad$ $360$の正の約数の個数を求めよ。

解説

素因数分解の問題について解説します。

素因数分解って何ですか？

素因数分解を理解するには、まず$\textcolor{red}{素数}$を知る必要があるよ。基本から確認していこう！

$100$以下の素数を効率よく見つけるには「$\textcolor{red}{エラトステネスのふるい}$」という方法が便利だよ。

$N$以下の素数を求めるには、$\sqrt{N}$以下の素数の倍数を順に消していけばいいんだ。

なぜ$\sqrt{N}$以下の素数だけでいいんですか？

もし$N$以下の合成数$n$があれば、$n=a \times b$（$a \leqq b$）と書けるよね。

このとき$a \leqq \sqrt{n} \leqq \sqrt{N}$だから、$\sqrt{N}$以下の素数で必ず割り切れるんだ。

$N=100$のとき $\sqrt{100}=10$ なので、$10$以下の素数 $2, 3, 5, 7$ の倍数を消していきます。

すると、$100$以下の素数は次の$25$個になります。

ある自然数$n$が素数かどうかを判定するときも同じ考え方が使えるよ。$\sqrt{n}$以下の素数で割り切れなければ、$n$は素数だと判定できるんだ。

素因数分解のやり方を教えてください！

素因数分解とは、自然数を$\textcolor{red}{素数の積}$で表すことだよ。

小さい素数から順に割っていくのがコツだね。

それでは$360$を素因数分解してみましょう。小さい素数$2, 3, 5, \cdots$で順に割っていきます。

よって、$\underline{360 = 2^3 \times 3^2 \times 5}$ となります。

素因数分解の結果は、素数を小さい順に並べて書くのが一般的だよ。

また、同じ素数が何回出てくるかを指数（累乗）で表すんだ。

素因数分解の結果は1通りしかないんですか？

いい質問だね！実は、$1$より大きい自然数の素因数分解は、順序を除いて$\textcolor{red}{ただ1通り}$に定まるんだ。

これを「$\textcolor{red}{算術の基本定理}$」というよ。

素因数分解を利用すると、約数の個数を簡単に求められるよ。

$360 = 2^3 \times 3^2 \times 5^1$ と素因数分解されたので、$360$の約数は $2^a \times 3^b \times 5^c$ の形で表すことができます。

ここで、$a$は$0, 1, 2, 3$の$4$通り、$b$は$0, 1, 2$の$3$通り、$c$は$0, 1$の$2$通りです。

この公式を使うと、$360$の正の約数の個数は

$(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = \underline{24}$個

となります。

素因数分解すると約数の個数がすぐ分かるんですね！

その通り！素因数分解は整数問題の基本だから、しっかりマスターしよう！

ここでは素因数分解について学習しました。

素数の定義やエラトステネスのふるいを使った素数の判定法、そして小さい素数から順に割っていく素因数分解の手順を確認しました。

素因数分解は約数の個数や総和を求める際にも活用できる、整数問題の基本テクニックです。ぜひ練習して使いこなせるようにしてくださいね！