こんにちは、じゃた。です。今回は素数をなるべく早く表示するプログラムを考えていきたいと思います。
言語はJavaです。

考え方、プログラム

　今回何をしたいのかと言うと、例えば、『「1.0×10^8」までの素数を全て表示しなさい。』みたいな問題があったとする。とりあえず表示できればよいのだが、何も考えずに進めていくと、最終的にかなり時間のかかるプログラムとなってしまうかもしれない。もちろん、プログラムに慣れている人であればそんなことはないのだろうが、まだあまり慣れていない人にとっては結構難しいと思う。今回は「5.0×10^6」までの素数を全て表示するプログラムを考えていきたいと思う。
　で、結局今回はどういったプログラムを書いていけばいいのか。”素数”とは、「1とその数字以外で割り切れない自然数」のことだ。つまり、2~その数字-1までで割っていき、一つでも割り切れる場合があれば”素数ではない”ということになる。例えば、

1. 「9」の場合

　9/2 … ×
　9/3 … ◯ -> 素数ではない
　9/4~は確かめなくてもよい。

2. 「11」の場合

　11/2 … ×
　11/3 … ×
　　…
　11/10 … × -> 2~(11-1)全ての場合で割り切れないため、素数
　
みたいな感じだ。もう少し考えてみると、偶数は必ず2で割り切れるはずであるから、そもそも確かめる必要がないことが分かる。また、偶数を確かめないとすると、確認していく数字の中に2で割り切れる数字は絶対にないということになる。以上を踏まえたうえで考えてみると、以下のようなプログラムが書ける。

public class Primenum{
    public static void main(String args[]){
        int flag = 0, num = 1;

        //3から「奇数」で割りきれるかどうかを確かめればよい。
        System.out.print(2+" ");
        for(int i = 3; i < 500000; i+=2) {
            flag = 0;
            for(int j = 3; j < i; j+=2){
                if(i%j == 0){
                    flag++;
                    break;
                }
            }

            if(flag == 0){
                System.out.print(i+" ");
                num++;
            }

            //300個表示したら改行
            if(num%300 == 0){
                System.out.println();
                num = 0;
            }
        }
        System.out.println();
    }
}

　実行テストをしてみれば分かると思うが、これではかなり遅い。では、どうやったら高速化できるか。
再確認となるが、素数とは「1とその数字以外で割り切れない自然数のこと」である。つまり、素数でない数字とは「その数字の平方根以下の数字に、少なくとも一つは約数が存在する」ということになる。
その数字をcとすると、”割り切れる”ということは、「a×b=c（a=bの場合もあり）」という式が成り立つ場合があるということである。もしa, b両方がcの平方根より大きい数字だった場合、「a×b>c」となってしまう。もしも分かりにくければ、”16″や”25″などで確認してみればよい。
　以上のことを踏まえると、”「その数の平方根以下の数字」かつ「奇数」”で割っていけば、素数かどうか判別できるということになる。

public class Primenum{
    public static void main(String args[]){
        int flag = 0, num = 1;

        //素数でない場合、少なくとも約数の一つは「自身の平方根以下の数」が含まれている。
        //「自身の平方根以下の数」かつ「奇数」で割り切れるかどうかを確かめればよい。
        System.out.print(2+" ");
        for (int i = 3; i < 500000; i += 2) {
            flag = 0;
            for (int j = 3; (j * j) <= i; j += 2) {
                if ((i % j) == 0) {
                    flag++;
                    break;
                }
            }

            if (flag == 0) {
                System.out.print(i+" ");
            }

            //300個表示したら改行
            if(num%300 == 0){
                System.out.println();
                num = 0;
            }
        }
        System.out.println();
    }
}

　始めのものに比べれば、だいぶ高速になったと思う。だが、まだ無駄がある。”「その数の平方根以下の数字」かつ「奇数」で割り切れるかどうか”を試し、一度でも割り切れたら”素数でない”と判定しているわけだが、”自身の平方根以下全ての奇数”で割る必要はない。
例えば、21で割り切れる数字は3でも7でも割り切れるはずである。「21=3×7」であるから、21で割り切れるならば3でも7でも割り切れるということは分かると思う。つまり、”「自身の平方根以下の数」かつ「素数」で割り切れるかどうか”を確かめればよい。

public class Primenum{
    public static void main(String args[]){
        int flag = 0;
        int list[] = new int[45000];
        int data_num = 1;

        //「自身の平方根以下の数」かつ「素数」で割り切れるかどうかを確かめればよい。
        //2を除いた素数のデータを配列に保管、「3からの素数」で割り切れるかどうかを確かめる。
        System.out.print(2+" "+3+" ");
        list[0] = 3;

        for (int i = 5; i < 500000; i += 2) {
            flag = 0;
            for (int j = 0; (list[j] * list[j]) <= i; j++) {
                if ((i % list[j]) == 0) {
                    flag++;
                    break;
                }
            }

            if (flag == 0) {
                System.out.print(i+" ");
                list[data_num] = i;
                data_num++;
            }

            //300個表示したら改行
            if((data_num+2)%300 == 0){
                System.out.println();
            }
        }
        System.out.println();
    }
}

　3つのプログラムを書いてみたが、私のレベルではこれが限界であった。もっと効率の良いプログラムが分かる方は、是非私に分かるよう丁寧な解説付きで教えてほしい。あと、数が多すぎて全部表示できないのどうにかしてくれぇ…

終わりに

自分なりに頑張って考えてみましたが、やっぱり練習をしっかりやって、いろんな人のプログラム見て学んでっていうことをやっていないと、たいした成長もせずに無駄な時間を過ごすだけですね…。去年から少しもレベルアップしていない気がしてとても悲しいですが、気にせずコツコツ勉強していきたいと思います。
最後まで読んでくれて本当にありがとう！See You Next Time！