素因数分解 約数 約数の総和 JavaScript
入力欄に好きな数値を入れて[実行]ボタンを押してください。
入力数値の素因数分解を実行し、全約数を求め、全約数の総和から完全数判定をします。
入力数値は JavaScript における確実な整数の最大値 (253 - 1 = 9007199254740991) 以下の15桁の数値まで対応しています。
$0, 1, 2, 3, \ldots$ と $1$ ずつ大きくなって数えられる数のことを自然数（natural number）といいます。
ここでは自然数の範囲内で数を考えます。
ある数を余りを出さずに割り切る数を約数（divisor）といいます。
素数（prime number）とは、その数自身 と $1$ の二個の自然数だけを約数に持つ自然数のことです。
$0, 1$ 以外の素数ではない数のことを合成数（composit number）といいます。
以下、素数かどうかを約数の個数で判定するプログラムです。
適度な範囲を入力して[チェック]ボタンを押してください。
から
までの自然数で、
約数を
$2$ 以上の全ての自然数は素数の積で表すことができます。
積を構成する素数のことを素因数（prime factor）といい、素因数の積で数を表すことを素因数分解（prime factorization）といいます。
素因数分解の際「素数の組み合わせ」はただ一通りに決まります。
この性質を素因数分解の一意性といいます。
例として $12$、$18$、$30$という数を考えてみましょう。
$12$ は 素数 $2$ が $2$ 個、素数 $3$ が $1$ 個、の積で表されます。
$18$ は 素数 $2$ が $1$ 個、素数 $3$ が $2$ 個、の積で表されます。
$30$ は 素数 $2$ が $1$ 個、素数 $3$ が $1$ 個、素数 $5$ が $1$ 個、の積で表されます。
次の式の右辺が素因数分解した式になります。
\begin{align*}
12 &= 2\cdot 2\cdot 3 \\
18 &= 2\cdot 3\cdot 3 \\
30 &= 2\cdot 3\cdot 5
\end{align*}
掛け算記号 「$\times$」 を省略記号 「$\cdot$」 で書いてます。
この後、特に誤解がない限り、省略記号も省略していきます。
ここで、$1$ は素数ではない を強調しておきます。
仮に $1$ が素数だとすると、「素因数分解の一意性」という性質が崩れてしまいます。
例えば 「$12 = 1\cdot 2\cdot 2\cdot 3$」 と表せたり、「$12 = 1\cdot 1\cdot 2\cdot 2\cdot 3$」 と表せたり、「$12 = 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 3$」 と表せたり、無限の素数の組み合わせが考えられてしまいます。
$1$ を素数とすると「素因数分解の一意性」という大変重要な性質が使えなくなってしまうことになります。
次に、表記を簡潔にするために累乗表記を導入します。
「自然数 $n$ を $2$ 回掛ける」を、右肩に指数を乗せて 「$n\cdot n=n^2$」 と表します。
「$n$ を $3$ 回掛ける」を 「$n\cdot n\cdot n = n^3$」 と表します。
「$n$ を $m$ 回掛ける」を 「$n\cdot n\cdot n\cdot\cdots\cdot n = n^m$」 と表します。
「$n$ を $1$ 回だけ掛ける」は 「$n=n^1$」 と表せます。
「$n$ を $1$ 回も掛けない」は 「$n^0=1$」 で表現できます。
累乗表記を用いると $12, 18, 30$ の素因数分解は、次の右辺のように書けます。
どのような素数の何個の組み合わせの積なのか分かりやすいです。
\begin{align*}
12 &= 2^2 3^1 \\
18 &= 2^1 3^2 \\
30 &= 2^1 3^1 5^1
\end{align*}
上の式の右辺から左辺を求めるのは簡単ですが、左辺から右辺を求めるのは結構大変です。
$12$ の場合にどのようにして素因数を求めるか、やってみましょう。
- $12$ を割り切る素数を探して、$2$ で割ると、割り切れて、商は $6$ になる。割り切れたので $12$ は $2$ を一つ素因数に持つことが分かる。（下式1行目）
- 一つ前の商の $6$ を割り切る素数を探して、$2$ で割ると、割り切れて、商は $3$ になる。割り切れたので $12$ は $2$ をもう一つ素因数に持つことが分かる。（下式2行目）
- 一つ前の商の $3$ を割り切る素数を探して、$3$ で割ると、割り切れて、商は $1$ になる。割り切れたので $12$ は $3$ を一つ素因数に持つことが分かる。（下式3行目）
- 商が $1$ になったので、これ以上割り切れる素数がないため、ここで終了（下式4）
\begin{align*}
\require{enclose}
\begin{array}{rl}
2 )\!\enclose{bottom}{12} & \qquad\rightarrow 2\mbox{が素因数} \\[-3pt]
2 )\!\enclose{bottom}{\phantom{0}6} & \qquad\rightarrow 2\mbox{が素因数} \\[-3pt]
3 )\!\enclose{bottom}{\phantom{0}3} & \qquad\rightarrow 3\mbox{が素因数} \\[-3pt]
\phantom{0 )}\!\enclose{}{\phantom{0}1} & \\[-3pt]
\end{array}
\end{align*}
\begin{align*}
&12 \mbox{ は、素因数 $2$ が $2$ 個、素因数 $3$ が $1$ 個、の積に分解される} \\
&12 = 2\cdot 2\cdot 3 = 2^2 3^1
\end{align*}
$18$ の場合をやってみましょう。
\begin{align*}
\require{enclose}
\begin{array}{rl}
2 )\!\enclose{bottom}{18} & \qquad\rightarrow 2\mbox{が素因数} \\[-3pt]
3 )\!\enclose{bottom}{\phantom{0}9} & \qquad\rightarrow 3\mbox{が素因数} \\[-3pt]
3 )\!\enclose{bottom}{\phantom{0}3} & \qquad\rightarrow 3\mbox{が素因数} \\[-3pt]
\phantom{0 )}\!\enclose{}{\phantom{0}1} & \\[-3pt]
\end{array}
\end{align*}
\begin{align*}
&18 \mbox{ は、素因数 $2$ が $1$ 個、素因数 $3$ が $2$ 個、の積に分解される} \\
&18 = 2\cdot 3\cdot 3 = 2^1 3^2
\end{align*}
$60$ の場合をやってみましょう。
\begin{align*}
\require{enclose}
\begin{array}{rl}
2 )\!\enclose{bottom}{60} & \qquad\rightarrow 2\mbox{が素因数} \\[-3pt]
2 )\!\enclose{bottom}{30} & \qquad\rightarrow 2\mbox{が素因数} \\[-3pt]
3 )\!\enclose{bottom}{15} & \qquad\rightarrow 3\mbox{が素因数} \\[-3pt]
5 )\!\enclose{bottom}{\phantom{0}5} & \qquad\rightarrow 5\mbox{が素因数} \\[-3pt]
\phantom{0 )}\!\enclose{}{\phantom{0}1} & \\[-3pt]
\end{array}
\end{align*}
\begin{align*}
&60 \mbox{ は、素因数 $2$ が $2$ 個、素因数 $3$ が $1$ 個、素因数 $5$ が $1$ 個、の積に分解される} \\
&60 = 2\cdot 2\cdot 3\cdot 5 = 2^2 3^1 5^1
\end{align*}
小さな数の場合は良いのですが、大きな数では割り切れる素数を見つけるのが大変になってきます。
仕組みを知る程度に素因数分解の手計算の練習をして、大きな数に関しては、コンピュータプログラムの力を借りて結果を確かめるとよいでしょう。
以下、範囲を指定して素因数分解を実行するプログラムです。
素因数分解の結果から素数か合成数か判定できます。
- 素因数が $1$ 個だけの数は「素数」です
- 素因数が $2$ 個以上の数は「合成数」です
から
までの自然数を
素因数を取り出す全ての組み合わせのパターンから、約数が全て求まります。
$5$ の素因数分解から全ての $5$ の約数 $\{1, 5\}$ を求めてみましょう。
\begin{align*}
5 &= 5^1\qquad \mbox{素因数分解} \\
1 &= 5^0\qquad \mbox{素因数から $5$ を $0$ 個、取り出した積} \\
5 &= 5^1\qquad \mbox{素因数から $5$ を $1$ 個、取り出した積} \\
\end{align*}
約数は全部で $(1+1)=2$ 個
$25$ の素因数分解から全ての $25$ の約数 $\{1, 5, 25\}$ を求めてみましょう。
\begin{align*}
25 &= 5^2\qquad \mbox{素因数分解} \\
1 &= 5^0\qquad \mbox{素因数から $5$ を $0$ 個、取り出した積} \\
5 &= 5^1\qquad \mbox{素因数から $5$ を $1$ 個、取り出した積} \\
25 &= 5^2\qquad \mbox{素因数から $5$ を $2$ 個、取り出した積} \\
\end{align*}
約数は全部で $(2+1)=3$ 個
$12$ の素因数分解から全ての $12$ の約数 $\{1, 2, 3, 4, 6, 12\}$ を求めてみましょう。
\begin{align*}
12 &= 2^2 3^1\qquad \mbox{素因数分解} \\
1 &= 2^0 3^0\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $0$ 個、取り出した積} \\
2 &= 2^1 3^0\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $0$ 個、取り出した積} \\
3 &= 2^0 3^1\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $1$ 個、取り出した積} \\
4 &= 2^2 3^0\qquad \mbox{素因数から $2$ を $2$ 個、$3$ を $0$ 個、取り出した積} \\
6 &= 2^1 3^1\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $1$ 個、取り出した積} \\
12 &= 2^2 3^1\qquad \mbox{素因数から $2$ を $2$ 個、$3$ を $1$ 個、取り出した積} \\
\end{align*}
約数は全部で $(2+1)(1+1)=3\cdot 2=6$ 個
$18$ の素因数分解から全ての $18$ の約数 $\{1, 2, 3, 6, 9, 12\}$ を求めてみましょう。
\begin{align*}
18 &= 2^1 3^2\qquad \mbox{素因数分解} \\
1 &= 2^0 3^0\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $0$ 個、取り出した積} \\
2 &= 2^1 3^0\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $0$ 個、取り出した積} \\
3 &= 2^0 3^1\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $1$ 個、取り出した積} \\
6 &= 2^1 3^1\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $1$ 個、取り出した積} \\
9 &= 2^0 3^2\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $2$ 個、取り出した積} \\
18 &= 2^1 3^2\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $2$ 個、取り出した積} \\
\end{align*}
約数は全部で $(1+1)(2+1)=2\cdot 3=6$ 個
$60$ の素因数分解から全ての $60$ の約数 $\{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\}$ を求めてみましょう。
\begin{align*}
60 &= 2^2 3^1 5^1\qquad \mbox{素因数分解} \\
1 &= 2^0 3^0 5^0\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $0$ 個、$5$ を $0$ 個、取り出した積} \\
2 &= 2^1 3^0 5^0\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $0$ 個、$5$ を $0$ 個、取り出した積} \\
3 &= 2^0 3^1 5^0\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $1$ 個、$5$ を $0$ 個、取り出した積} \\
4 &= 2^2 3^0 5^0\qquad \mbox{素因数から $2$ を $2$ 個、$3$ を $0$ 個、$5$ を $0$ 個、取り出した積} \\
5 &= 2^0 3^0 5^1\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $0$ 個、$5$ を $1$ 個、取り出した積} \\
6 &= 2^1 3^1 5^0\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $1$ 個、$5$ を $0$ 個、取り出した積} \\
10 &= 2^1 3^0 5^1\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $0$ 個、$5$ を $1$ 個、取り出した積} \\
12 &= 2^2 3^1 5^0\qquad \mbox{素因数から $2$ を $2$ 個、$3$ を $1$ 個、$5$ を $0$ 個、取り出した積} \\
15 &= 2^0 3^1 5^1\qquad \mbox{素因数から $2$ を $0$ 個、$3$ を $1$ 個、$5$ を $1$ 個、取り出した積} \\
20 &= 2^2 3^0 5^1\qquad \mbox{素因数から $2$ を $2$ 個、$3$ を $0$ 個、$5$ を $1$ 個、取り出した積} \\
30 &= 2^1 3^1 5^1\qquad \mbox{素因数から $2$ を $1$ 個、$3$ を $1$ 個、$5$ を $1$ 個、取り出した積} \\
60 &= 2^2 3^1 5^1\qquad \mbox{素因数から $2$ を $2$ 個、$3$ を $1$ 個、$5$ を $1$ 個、取り出した積} \\
\end{align*}
約数は全部で $(2+1)(1+1)(1+1)=3\cdot 2\cdot 2=12$ 個
一般の $2$ 以上の自然数 $n$ が $m$ 種類の素数 $p_1, p_2, \cdots, p_m$ をそれぞれ $i_1, i_2, \cdots, i_m$ 個素因数として持つとき、次のようにして、全ての約数 $d_k$ を求められる。
\begin{align*}
n &= p_1^{i_1} p_2^{i_2} \cdots p_m^{i_m}\qquad \mbox{素因数分解} \\
d_k &= p_1^{j_1} p_2^{j_2} \cdots p_m^{j_m}\qquad \mbox{素因数から $p_1$ を $0\le j_1\le i_1$ 個、$p_2$ を $0\le j_2\le i_2$ 個、$\cdots$、$p_m$ を $0\le j_m\le i_m$ 個、取り出した積} \\
\end{align*}
約数は全部で $(i_1+1)(i_2+1)\cdots (i_m+1)$ 個
約数には大きさ順に $k$ の通し番号を付ける
ある自然数 $n$ の全ての約数の総和 $S_n$ を求めます。
例として $n=5, 12, 18, 25, 60$ の場合を考えてみましょう。
$5$ の 全約数 $\{1, 5\}$ の和 $S_5$
\begin{align*}
S_5
&= 1 + 5 \\
&= 6
\end{align*}
$12$ の 全約数 $\{1, 2, 3, 4, 6, 12\}$ の和 $S_{12}$
\begin{align*}
S_{12}
&= 1 + 2 + 3 + 4 + 6 + 12 \\
&= 28
\end{align*}
$18$ の 全約数 $\{1, 2, 3, 6, 9, 18\}$ の和 $S_{18}$
\begin{align*}
S_{18}
&= 1 + 2 + 3 + 6 + 9 + 18 \\
&= 39
\end{align*}
$25$ の 全約数 $\{1, 5, 25\}$ の和 $S_{25}$
\begin{align*}
S_{25}
&= 1 + 5 + 25 \\
&= 31
\end{align*}
$60$ の 全約数 $\{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\}$ の和 $S_{60}$
\begin{align*}
S_{60}
&= 1 + 2 + 3 + 4 + 5 + 6 + 10 + 12 + 15 + 20 + 30 + 60 \\
&= 168
\end{align*}
$n$ の全ての約数の総和 $S_n$ には別の求め方があります。
素因数分解を利用すれば、必ずしも全ての約数を先に求める必要はありません。
$5=5^1$ の 全約数の総和 $S_5$
\begin{align*}
S_5
&= 5^0 + 5^1 \\
&= 1 + 5 \\
&= 6
\end{align*}
$12=2^2 3^1$ の 全約数の総和 $S_{12}$
\begin{align*}
S_{12}
&= \left(2^0 + 2^1 + 2^2\right)\left(3^0 + 3^1\right) \\
&= \left(1 + 2 + 4\right)\left(1 + 3\right) \\
&= 7\cdot 4 \\
&= 28
\end{align*}
$18=2^1 3^2$ の 全約数の総和 $S_{18}$
\begin{align*}
S_{18}
&= \left(2^0 + 2^1\right)\left(3^0 + 3^1 + 3^2\right) \\
&= \left(1 + 2\right)\left(1 + 3 + 9\right) \\
&= 3\cdot 13 \\
&= 39
\end{align*}
$25=5^2$ の 全約数の総和 $S_{25}$
\begin{align*}
S_{25}
&= 5^0 + 5^1 + 5^2 \\
&= 1 + 5 + 25 \\
&= 31
\end{align*}
$60=2^2 3^1 5^1$ の 全約数の総和 $S_{60}$
\begin{align*}
S_{60}
&= \left(2^0 + 2^1 + 2^2\right)\left(3^0 + 3^1\right)\left(5^0 + 5^1\right) \\
&= \left(1 + 2 + 4\right)\left(1 + 3\right)\left(1 + 5\right) \\
&= 7\cdot 4\cdot 6 \\
&= 168
\end{align*}
なぜ、上のやり方で上手くいくか？素因数が 一種類の時はすぐにわかると思います。
素因数がの二種類以上の場合、括弧の掛け算の展開を先に行えば、うまくいくことが理解できます。
括弧を展開したときに全ての約数のパターンの和が出てきます。
$12=2^2 3^1$ の 全約数 $(2+1)(1+1)$ 個の和 $S_{12}$
\begin{align*}
S_{12}
&= \left(2^0 + 2^1 + 2^2\right)\left(3^0 + 3^1\right) \\
&= 2^0 3^0 + 2^1 3^0 + 2^2 3^0 + 2^0 3^1 + 2^1 3^1 + 2^2 3^1 \\
&= 1\cdot 1 + 2\cdot 1 + 4\cdot 1 + 1\cdot 3 + 2\cdot 3 + 4\cdot 3 \\
&= 1 + 2 + 4 + 3 + 6 + 12 \\
&= 1 + 2 + 3 + 4 + 6 + 12
\end{align*}
$18=2^1 3^2$ の 全約数 $(1+1)(2+1)$ 個の和 $S_{18}$
\begin{align*}
S_{18}
&= \left(2^0 + 2^1\right)\left(3^0 + 3^1 + 3^2\right) \\
&= 2^0 3^0 + 2^1 3^0 + 2^0 3^1 + 2^1 3^1 + 2^0 3^2 + 2^1 3^2 \\
&= 1\cdot 1 + 2\cdot 1 + 1\cdot 3 + 2\cdot 3 + 1\cdot 9 + 2\cdot 9 \\
&= 1 + 2 + 3 + 6 + 9 + 18
\end{align*}
$60=2^2 3^1 5^1$ の 全約数 $(2+1)(1+1)(1+1)$ 個の和 $S_{60}$
\begin{align*}
S_{60}
&= \left(2^0 + 2^1 + 2^2\right)\left(3^0 + 3^1\right)\left(5^0 + 5^1\right) \\
&= 2^0 3^0 5^0 + 2^1 3^0 5^0 + 2^2 3^0 5^0 + 2^0 3^1 5^0 + 2^1 3^1 5^0 + 2^2 3^1 5^0 + 2^0 3^0 5^1 + 2^1 3^0 5^1 + 2^2 3^0 5^1 + 2^0 3^1 5^1 + 2^1 3^1 5^1 + 2^2 3^1 5^1 \\
&= 1\cdot 1\cdot 1 + 2\cdot 1\cdot 1 + 4\cdot 1\cdot 1 + 1\cdot 3\cdot 1 + 2\cdot 3\cdot 1 + 4\cdot 3\cdot 1 + 1\cdot 1\cdot 5 + 2\cdot 1\cdot 5 + 4\cdot 1\cdot 5 + 1\cdot 3\cdot 5 + 2\cdot 3\cdot 5 + 4\cdot 3\cdot 5\\
&= 1 + 2 + 4 + 3 + 6 + 12 + 5 + 10 + 20 + 15 + 30 + 60 \\
&= 1 + 2 + 3 + 4 + 5 + 6 + 10 + 12 + 15 + 20 + 30 + 60
\end{align*}
一般の $2$ 以上の自然数 $n$ が $m$ 種類の素数 $p_1, p_2, \cdots, p_m$ をそれぞれ $i_1, i_2, \cdots, i_m$ 個素因数として持つとき、次のようにして、全ての約数 $(i_1+1)(i_2+1)\cdots (i_m+1)$ 個の和 $S_n$ を求められる。
\begin{align*}
n &= p_1^{i_1} p_2^{i_2} \cdots p_m^{i_m}\qquad \mbox{素因数分解} \\
S_n &= \left(p_1^0 + p_1^1 + p_1^2 + \cdots + p_1^{i_1}\right)\left(p_2^0 + p_2^1 + p_2^2 + \cdots + p_1^{i_2}\right)\cdots\left(p_m^0 + p_m^1 + p_m^2 + \cdots + p_m^{i_m}\right)
\end{align*}
ちなみに「和の記号 $\sum$」と「積の記号 $\prod$」を使うと次の式で表現することができます。
\begin{align*}
n &= \prod_{l=1}^m p_l^{i_l}\\
S_n &= \prod_{l=1}^m \left(\sum_{j_l=0}^{i_l}p_l^{j_l}\right)
\end{align*}
ある数の全約数から自分自身を抜いた約数の和が自分自身と等しくなるとき、その数を完全数（perfect number）といいます。
具体例を見た方が分かりやすいでしょう。
$6$ や $28$ は完全数です。
$6$ の約数は $\{1, 2, 3, 6\}$、この約数の中から $6$ 自身を除いた $\{1, 2, 3\}$ の和は $6$ 自身と等しくなる。
\begin{align*}
1 + 2 + 3 = 6
\end{align*}
$28$ の約数は $\{1, 2, 4, 7, 14, 28\}$、この約数の中から $28$ 自身を除いた $\{1, 2, 4, 7, 14\}$ の和は $28$ と等しくなる。
\begin{align*}
1 + 2 + 4 + 7 + 14 = 28
\end{align*}
完全数には次のような性質があります。
2以上の自然数 $n$ の全約数の総和を $S_n$ とする。
完全数では以下の性質が成り立つ。
\begin{align*}
S_n - n &= n\qquad\fbox{全約数の総和から自分自身を引くと自分自身になる}\\
S_n &= 2n\qquad\fbox{移項すると、全約数の総和が自分自身の $2$ 倍に等しい}
\end{align*}
紀元前三世紀頃の古代ギリシャでは $6, 28, 496, 8128$ の完全数が知られていて、神聖な数として扱われていました。
5番目の完全数 $33550336$ は 1456年に発見されました。
完全数は素数の研究との関係もあり、これまでに詳しく調べられています。
コンピュータの発達により2018年1月に50番目の完全数が見つかりました（Largest Known Prime Number: 277,232,917-1）。
「完全数は無限に存在するのか？」「奇数の完全数は存在するのか？」等の未解決問題があります。
ある数の全約数から自分自身を抜いた約数の和が自分自身より小さくなるとき、その数を不足数（deficient number）といいます。
不足数では次の性質が成り立ちます。
\begin{align*}
S_n - n &\lt n\qquad\fbox{全約数の総和から自分自身を引くと自分自身より小さくなる}\\
S_n &\lt 2n\qquad\fbox{移項すると、全約数の総和が自分自身の $2$ 倍より小さい}
\end{align*}
ある数の全約数から自分自身を抜いた約数の和が自分自身より小さくなるとき、その数を過剰数（abundant number）といいます。
過剰数では次の性質が成り立ちます。
\begin{align*}
S_n - n &\gt n\qquad\fbox{全約数の総和から自分自身を引くと自分自身より大きくなる}\\
S_n &\gt 2n\qquad\fbox{移項すると、全約数の総和が自分自身の $2$ 倍より大きい}
\end{align*}