小話３

エラストテネスのふるい
素因数分解にとても使える手法である。まず原理から紹介しようと思う。平易な言葉で述べてゆくので言葉の厳密な意味は見ていないことにする。自然数は自然数の積で構成されている。これらの自然数をはじめの自然数の因数と言う。初めの自然数をNと言うことにする。とりあえず、Nを積で平均しよう。つまり、√をつけてみよう、ということ。
√N。
ここで、√Nより大きいNの因数を取ってくる。それをaとすると、aの２乗はNより大きくなる。だから、Nの因数を２つに分けたとき、√Nより大きい因数を一つとってくると、あと一つは√Nより小さい因数となる。
　このような理由で、√N以下の数で割ることで、Nは因数２つにわけることができる。割ることができない場合はNは素数である。そのようにして手に入れた、２つの因数に対して同じ操作を繰り返す。そして、因数が素数になるまでこれまで操作を繰り返す。そうすることで、因数分解する数が小さくなるので、早い操作が可能になり、とても便利である。
　ここで合わせて使いたいのが、２と３と４と５と９が因数にふくまれているのかと言うことの判定法である。数学的にはひどいもんだが、安易な言葉を使うと、自然数の２つに一つは２を因数に持ち、３つに一つは３を因数に持つのである。そのため、この判定は非常に役立つのである。
　２の判定法は下一桁が偶数であるか。そうであれば２を因数に含む。３の判定法は各桁の和が３で割り切れるか。４の場合は下二桁が割り切れるか。５は下一桁が０か５。９は各桁の和が９で割り切れること。７は少し難しい。これらの解説は数多あるサイトに委ねることにする。
試しに28938を素因数分解してみよう。
下二桁に注目。おっ、４では割れないが、２では割れる。
14469。
各桁を足してみよう。1+4+4+6+9=24。よし。割れる。足したのが大きかったときはそれも足して考えればいい。2+4=6。うん。割れる。と言うことで
4823。
これは２でも３でも５でも割れない。エラストテネスのふるいを発動。
√4823=69.44…
70までの素数で考えよう。次に小さい7で割ってみる。割れた！
689。
もう一息。√689=26.24…つぎは11……割れない。では13はどうだろう。できた。
53。
最後に√53=7.28…と言うことで、8まで(7まで)の素数で53を割るけれども割れない。よし、53は素数。
素因数分解が完了しました。
14469=2×3×7×13×53