効率化された試し割りによる素数判定【細かすぎるコード解説:C言語編】
14622回の除算で1000以下の素数を求める
手がかり
とでしか割り切れない整数(素数)を探すとき、それより小さい素数で割り切れないものは、その他の整数(素数の倍数)でも割り切れない。
そのため、より小さいすべての素数で割ってみて割り切れるかのみ調べればよい。
プログラムのソースコード【細かすぎる注釈つき】
#include <stdio.h> int main(void) { //2以上1000以下の整数をnと表すことにする //つまり、整数nの中から素数を探すことになる int n; //除算回数を数えるカウンターを用意 unsigned long counter=0;/*unsigned long…長い桁数の非負整数を格納できる箱の名称(型)*/ //素数を入れる箱を500個用意する //2以外の素数はすべて奇数であり、1から1000までの数の中に奇数は500個しかない //そのうち1は素数ではなく、代わりに2は素数であるから、 //結局素数を入れる箱は500個で足りる int prime[500]; //i番目の素数をprime[i]と表すことにする int i; //既に見つけた素数の個数をptrとする。現時点ではまだ0である int ptr=0; //2と3は素数である prime[ptr++]=2;/*prime[0]=2と記憶した後に、ptrの値を1つ増やす(見つけた素数の個数が1になる)*/ prime[ptr++]=3;/*prime[1]=3と記憶した後に、ptrの値を1つ増やす(見つけた素数の個数が2になる)*/ //このように、小さい数から順に素数を探していくから、 //番号が若い素数の方が小さい素数である //現時点で見つかっている素数2個(prt=2)のうち最大のものはprime[1]=3であるように、 //これまで見つけたptr個の素数のうち最大のものは、prime[ptr-1]で表される //5以上1000以下の数の中から素数を探す for (n=5 ; n <= 1000; n+=2)/*5から始まって2ずつ増やしていくことで、奇数のみが対象になる*/ { //これまで見つけた素数prime[0]~prime[ptr-1]すべてで割ってみる //しかし、これから見つける素数はすべて奇数であるので、2で割り切れる数(偶数)は最初から除外してよい //よってprime[0]である2で割る必要はないので、3=prime[1]~prime[ptr-1]で割ってみる for ( i = 1; i < ptr; i++) { counter++;/*除算回数が1増える*/ if (n % prime[i] ==0)/*もし整数n(>4)がそれより小さい素数で割り切れたなら*/ { break; /*nは素数ではないので、もう他の数で割る必要はない⇒このforから追放*/ } //ここでi++が実行され、iの値が1増える //割り切れなかったものはこのforの冒頭に戻り、iが1大きな値に書き換えられたforの中身を繰り返す // (つまりより大きい素数で割られる) } //途中でforを追放されたものはここに到達している //まだiの値がptrよりはるかに小さい段階で中断されているので、 //ptr=iという条件を満たさず、if(ptr==1){}はスルーしてこのまま外側のforからも抜けることになる //最大素数prime[ptr-1]までのすべての素数で割り切れなかったものは、 //最後までbreakで抜けることなく、後処理i++を受けてここに到達する //つまり、最大素数での最後の除算をする段階ではi=ptr-1だが、その後のi++によって今はi=ptrとなっている //これは次のif文も実行されることになる if (ptr == i)/*i=ptrなら(これまで見つけたprime[ptr-1]までのすべての素数で割り切れなかったら)*/ { prime[ptr++]=n;/*そんな整数nを新たな素数prime[ptr]として登録する *(登録した後に、登録済み素数の数が1増える) */ } //ここでn+=2が実行され、nの値が2増える //外部forの冒頭に戻り、2大きな整数nについて全体の処理が再度行われる //このようにして、1000以下の整数をすべて登録済み素数で割って、選別する } //1000以下の整数すべての選別が終わると、ここに到達する //最終的に登録された素数すべて(prime[1]~prime[ptr-1])を一覧で表示する for ( i = 0; i < ptr; i++) { printf("%d\n",prime[i]); } //除算回数を表示する printf("乗除を行った回数:%lu\n",counter); return (0); }
3774回の乗算・除算で1000以下の素数を求める
強力な武器
改良版プログラムのソースコード【細かすぎる注釈つき】
変更した箇所にのみ補足説明を加えている。
#include <stdio.h> int main(void) { int n; //乗算・除算回数を数えるカウンターを用意 unsigned long counter=0; int prime[500]; int i; int ptr=0; prime[ptr++]=2; prime[ptr++]=3; for (n=5 ; n <= 1000; n+=2) { //2つの状態のどちらか(ONかOFFか)を判定するために使う変数をフラグという //今回は割り切れたか否かを判定する用に使う int flag = 0;/*初期値は0(フラグを下ろしておく)*/ //nの平方根以下のすべての素数で割ってみる //『素数pがnの平方根以下』という条件は、両辺2乗して『pの2乗がn以下』と言い換えられる for ( i = 1; counter++ , prime[i]*prime[i] <= n; i++) /*《A,B …AとBを順に実行し、Bの値を返す》 *for内部を実行するかの判定をするのはprime[i]*prime[i] <= nだが、 *判定の度に乗算*をカウントするということ */ { counter++; if (n % prime[i] ==0)/*割り切れたなら*/ { flag = 1; /*フラグを上げる*/ break; } } if (!flag) /*flag=0(フラグが下がったまま)なら*/ { prime[ptr++]=n;/*割り切れなかったということなので、素数として登録*/ } } for ( i = 0; i < ptr; i++) { printf("%d\n",prime[i]); } printf("乗除を行った回数:%lu\n",counter); return (0); }
コード引用元
今回掲載したコードのベースとなっているのは、柴田望洋先生の著書明解C言語入門編の109・111ページに掲載されているサンプルコードです。 説明の都合上、変数の名称や変数宣言の順序を変えています。また、括弧のレイアウトは自分好みに変えています。
定理の証明に関する参考文献
現在LaTeXで制作中の整数論ノートに今回素数判定に用いた定理の証明も掲載予定です。 厳密な証明ではないですが、コード引用元の書籍では正方形の図によってわかりやすく導出されています。 厳密な証明を追いかけたい方にはモノグラフ 整数をオススメします(が、絶版なんだよなあ…)。