素数
Prime number
1は素数ではない。(定義による)
2は素数である。(自明)
3は素数である。2で割ると1余る。
4は素数ではない。2で割ると割り切れる。
自然数を、もう一つの自然数で割る割り算で、割り切れる場合、割った数、および割った結果得られた数は、約数と呼ばれる。 素数は、1以外の数で、約数が2つの数ということができる。
すべての整数は素数を掛け合わせた数となる。
なぜならば、素数ではない数は素数で割れる数であり、割った時に得られた値とその素数との掛け算になるため。
割った時に得られた値はさらに同じように割ることができる。この繰り返しは必ず素数の掛け算となる。
すべての整数は、それぞれ異なる素数の組み合わせを掛け合わせた数になる。
もしも、同じ素数の組み合わせを掛け合わせた数であれば同じ数になるため。
1 = 1
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 3 * 2
7 = 7
8 = 2 * 4 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
素数を求める方法
素数の倍数を整数の一覧表から消していく。消されずに残った数が素数となる。
正の整数を素数の掛け算に分解することを素因数分解と呼ぶ 表現を簡単にするために、素数の出現順番号(1以上の自然数)から素数を求める写像を$ p(n)とする。
$ p(1) = 2
$ p(2) = 3
$ p(3) = 5
$ \dots
この$ p(n)について、少なくとも単純な計算式で求める方法は見つかっていない。
トートロジーになってしまっているが、以下のように考えることができる。
素因数分解したときに素数の乗算回数の数列が得られると考えればよい。
$ P_k(2) = \{1, 0, 0, 0, \dots\}
$ P_k(3) = \{0, 1, 0, 0, \dots\}
$ P_k(4) = \{2, 0, 0, 0, \dots\}
$ P_k(5) = \{0, 0, 1, 0, \dots\}
$ P_k(6) = \{1, 1, 0, 0, \dots\}
$ P_k(7) = \{0, 0, 0, 1, \dots\}
$ P_k(8) = \{3, 0, 0, 0, \dots\}
この数列は自然数ごとに必ず異なる。
乗算はこの無限次元のベクトルの加算と考えればよい。
$ P_k(2) = \{1, 0, 0, 0, \dots\}
$ P_k(3) = \{0, 1, 0, 0, \dots\}
$ P_k(2) + P_k(3)
$ = \{1, 0, 0, 0, \dots\} + \{0, 1, 0, 0, \dots\}
$ = \{1, 1, 0, 0, \dots\}
$ = P_k(6)
素因数分解がどうして難しいのか?
実際に除算してみないと余りがでるかどうか分からない。
どの数なら余りが0になるかどうかわからない。単純に順番に試しても、$ \Omicron(n)時間かかってしまう。
素数かどうかの判定方法