おおきな数字に対して、素数リストを作るためのプログラム

※サイト運営にサーバーは必須です※
～ロリポップ！はコスパのよい初心者向けサーバーです～

はじめに

素数のリストを作りたい場合、エラトスネスの篩に基づいたプログラムはよく使われる。

しかし、ある程度（というか、かなり）大きな数を取り扱いたいと考えた場合、ある問題に直面する。

それは、「メモリ不足」だ。

例えば、1000までの素数リストを作る際、1～1000の数字が素数か素数でないか覚えておくための配列を宣言する必要がある。

C#であれば、以下のようなコードで、素数か素数でないか真偽を入れておく配列が宣言される。

bool[] n_list = new bool[1000] ;

※ネット上では、boolでなくintで宣言するプログラムを書いている人もいるが、メモリ的には、真偽の2パターンしか入らないboolの方がメモリの観点で得なはず。

数字が1000までなら、問題は起きないが、これが1000でなく１億とかになると、問題になる。

例えばintを1つ宣言するには、4バイト必要。boolだと、(おそらく)1バイト。

ここでは、bool型で宣言すると考える。
1000までの数字に対応するメモリを用意するのに1KB(1000バイト)
100万までの数字に対応するメモリを用意するのに1MB(1000KB)
10億までの数字に対応するメモリを用意するのに1GB(1000MB)

普通のパソコンでメモリは、2~32GB程度。

実際には、全てのメモリをエラトスネスの篩のために全力投球することはできない。OSを動かすためなどにメモリが必要なはず。

それを考えると、1GB必要となる10億の数字をいっぺんに扱うのは、パソコンによってかなり厳しかったりする。

※タスクマネージャーを立ち上げておくと、どのぐらいのメモリを食っているかリアルタイムで見ることができる。私のパソコン(メモリ4GB)で、20億のエラトスネスの篩のプログラムは一応動いた(最後まで、実行が完了するかどうかは確認していない)。容量は2000MB近く確保されていたので、上の説明はそんなにずれてはいないだろう。

※このぐらいの数字になると、int型で扱える数字の最大値（およそ21億）に対しても注意を払う必要が出てくる。気を付けないとオーバーフローする危険がある。

この記事では、大きな数字でも安定して、エラトスネスの篩が動くようなプログラムを考えたい。

※単純にエラトスネスの篩を実装した場合のプログラムがどんなもんか確認したい場合は、以下の記事を参照
→エラトステネスの篩の素数判定プログラム(c#)

※追記：boolはプログラムによって容量が違っていたりする。0と1だけ扱うのだから1ビットで済みそうな気もするが、実際にはプログラムの言語やバージョンでbool型に必要な容量に違いが存在する。(1byte=8bit。8ビットが集まって1バイト) 。

理由は、ちょっとよくわからないが、プログラムで扱う最低容量が、1バイトだから、bool に対しても、1バイトは最低でも確保されていることがあるらしい。プログラムの言語によって、2バイトだったり、場合によっては、intと同じ４バイトあったりする。4バイト確保されているパターンの場合は、intへの型変換の関係上で確保されていたりするためと思われる。

確実に1バイトで済ませたい場合は、0～255の数字を扱うbyte型を採用するのが一番無難な気がする。

プログラムのアルゴリズム

単純に1万（10000）までの素数を求めたいと考えたとする(n_ini=10000)。

この1万を分割し、100の単位に分ける(dn=100)。

最初の１回目は1～100までの数字を考える(配列はn_list[0]~ n_list[99])。

100の平方根（√）は10なので、2～10までの数字で割り切れなったら、その数字は素数と考える。

※プログラム上、2を特別扱いした方が早くなる。2で割る前処理が終わった後は、3、5、7、9の奇数だけを取り出して、割りきれるかどうか判定している。

2回目は、101～200を考える。

2回目以降から一部処理が変わる。1回目で得られた、素数リスト(p_list)をもとに、素数の探索を行うようになる。

まず、2だけ先に処理する。その後、200の平方根（√）の整数部に対応する14以下の数字で、かつ、素数の数をピックアップする。ここでは、3、5、7、11、13の数字を使って探索をする。

※プログラム上は、101～200がn_list[0]~ n_list[99]に対応。offsetとして100だけゲタをはかして、１回目と同様の処理をする。

これが終わったら、101～200で素数判定を受けた数字だけを、素数のリストに加えていく。

これを１万まで繰り返す。

以上のような感じで計算している。

確保するメモリは、1～10000でなく、1～100までの分があれば問題ない。
※正確には、素数を記録するためなどにもメモリは使われている。

プログラム

プログラムは以下のようになる。
言語はC#。VisualStudio2015のコンソールアプリケーションとして作成。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using System.Diagnostics;
using static System.Math;
using System.IO;

//using System.Collections.Generic;

namespace prime_list
{
    class Program
    {
        static void Main(string[] args)
        {

            Stopwatch st = new Stopwatch();
            st.Start();



            int n_ini = 1000000000;//この数字まで、素数を調べる
            int dn = 10000;//刻み幅（分割単位）
            int a = n_ini/dn; //a*dn+b(配列の大きさに相当)
            int b = n_ini % dn;//b余り（bが0でないときの処理はそのうち実装。このプログラムではn_ini/dnが割り切れる場合を想定。つまりb=0）
            int n_root;//ルート
            int index = 1;//「何」番目の素数か記録する

            List<int> p_list = new List<int>();//素数を覚えておくリスト
            p_list.Add(2);//2を素数リストにあらかじめ追加しておく

            bool[] n_list = new bool[dn];//bool の初期はfalse

            //出力準備
            string file_name = "prime_list" + n_ini + ".txt";
            FileStream fs = new FileStream(file_name, FileMode.Create);//上書き保存する
            StreamWriter sw = new StreamWriter(fs);





            //最初の1回目
            //WriteLine(2 + "\r\n");
            sw.Write(index + "\t" +2 + "\r\n");
            index += 1;

            for (int j = 2; 2 * j - 1 < dn; ++j)
            {
                n_list[2* j - 1] = true;
            }


            n_root = (int)Sqrt(dn);

            for (int i=2; (i+1)<= n_root;i+=2)
            {
                if(n_list[i] == false)
                {
                    for (int j = (i + 1); (i + 1) * j - 1 < dn; j+=2)
                    {
                        n_list[(i + 1) * j - 1] = true;
                    }
                }

            }



            for (int k = 2; k < dn; k+=2)
            {
                if (n_list[k] == false)
                {
                    //WriteLine(k+1 + "\r\n");
                    sw.Write(index+"\t"+ Convert.ToString(k + 1) + "\r\n");
                    index += 1;
                    p_list.Add(k+1);
                }
            }

            int offset;
            int max_num;

            //2回目以降
            for (int t = 1; t < a; ++t)
                {

                offset = dn * t;
                max_num= dn * (t+1);
                n_root = (int)Sqrt(max_num);

                //n_list = new bool[dn];//配列の初期化(これで初期化するとメモリ的に損しないか？)
                //n_listの初期化
                for (int j=0; j < dn; ++j)
                {
                    n_list[j] = false;
                }


                //2だけ前処理
                for (int j = (offset/2) + 1; 2 * j - 1  < max_num; ++j)
                {
                    n_list[2 * j - 1 - offset] = true;
                }

                //3以上の素数の処理
                for (int i = 1; p_list[i] <= n_root; ++i)
                {
                    int m;
                    m= (int)Ceiling(((double)(offset+1)/(double)(p_list[i])));
                    if (m % 2 == 0)
                    {
                        m += 1;
                    }
                    for (int j = m; p_list[i] * m - 1 < max_num; m += 2)
                    {
                        n_list[p_list[i] * m - 1 - offset] = true;
                    }
                }

                //結果の処理
                for (int k = 0; k < dn; k += 2)
                    {
                        if (n_list[k] == false)
                        {
                        //WriteLine(k + 1 + offset + "\r\n");
                        sw.Write(index + "\t" + Convert.ToString(k + 1+ offset) + "\r\n");
                        index += 1;
                        p_list.Add(k + 1 + offset);
                        }
                    }

            }            //2回目以降の処理終了


            //最後にbが0でなかったときの処理(未実装)




            st.Stop();
            //WriteLine(st.Elapsed);
            sw.Write("//測定時間は" + st.Elapsed + "\r\n");
            sw.Close();//ファイルを閉じる



        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using static System.Console;

using System.Diagnostics;

using static System.Math;

using System.IO;

//using System.Collections.Generic;

namespace prime_list

{

class Program

{

static void Main(string[] args)

{

Stopwatch st = new Stopwatch();

st.Start();

int n_ini = 1000000000;//この数字まで、素数を調べる

int dn = 10000;//刻み幅（分割単位）

int a = n_ini/dn; //a*dn+b(配列の大きさに相当)

int b = n_ini % dn;//b余り（bが0でないときの処理はそのうち実装。このプログラムではn_ini/dnが割り切れる場合を想定。つまりb=0）

int n_root;//ルート

int index = 1;//「何」番目の素数か記録する

List<int> p_list = new List<int>();//素数を覚えておくリスト

p_list.Add(2);//2を素数リストにあらかじめ追加しておく

bool[] n_list = new bool[dn];//bool の初期はfalse

//出力準備

string file_name = "prime_list" + n_ini + ".txt";

FileStream fs = new FileStream(file_name, FileMode.Create);//上書き保存する

StreamWriter sw = new StreamWriter(fs);

//最初の1回目

//WriteLine(2 + "\r\n");

sw.Write(index + "\t" +2 + "\r\n");

index += 1;

for (int j = 2; 2 * j - 1 < dn; ++j)

{

n_list[2* j - 1] = true;

}

n_root = (int)Sqrt(dn);

for (int i=2; (i+1)<= n_root;i+=2)

{

if(n_list[i] == false)

{

for (int j = (i + 1); (i + 1) * j - 1 < dn; j+=2)

{

n_list[(i + 1) * j - 1] = true;

}

for (int k = 2; k < dn; k+=2)

{

if (n_list[k] == false)

{

//WriteLine(k+1 + "\r\n");

sw.Write(index+"\t"+ Convert.ToString(k + 1) + "\r\n");

index += 1;

p_list.Add(k+1);

}

int offset;

int max_num;

//2回目以降

for (int t = 1; t < a; ++t)

{

offset = dn * t;

max_num= dn * (t+1);

n_root = (int)Sqrt(max_num);

//n_list = new bool[dn];//配列の初期化(これで初期化するとメモリ的に損しないか？)

//n_listの初期化

for (int j=0; j < dn; ++j)

{

n_list[j] = false;

}

//2だけ前処理

for (int j = (offset/2) + 1; 2 * j - 1 < max_num; ++j)

{

n_list[2 * j - 1 - offset] = true;

}

//3以上の素数の処理

for (int i = 1; p_list[i] <= n_root; ++i)

{

int m;

m= (int)Ceiling(((double)(offset+1)/(double)(p_list[i])));

if (m % 2 == 0)

{

m += 1;

}

for (int j = m; p_list[i] * m - 1 < max_num; m += 2)

{

n_list[p_list[i] * m - 1 - offset] = true;

}

//結果の処理

for (int k = 0; k < dn; k += 2)

{

if (n_list[k] == false)

{

//WriteLine(k + 1 + offset + "\r\n");

sw.Write(index + "\t" + Convert.ToString(k + 1+ offset) + "\r\n");

index += 1;

p_list.Add(k + 1 + offset);

}

} //2回目以降の処理終了

//最後にbが0でなかったときの処理(未実装)

st.Stop();

//WriteLine(st.Elapsed);

sw.Write("//測定時間は" + st.Elapsed + "\r\n");

sw.Close();//ファイルを閉じる

}

注意点

スピードを稼ぐために、2を別処理している。
なるべく処理するスピードを上げるために、色々工夫をしているが、その分、プログラムはわかりづらくなっている。プログラムを書いた本人が言うのもなんだが、あまり見たくない。
Falseの場合が素数で、Trueなら素数でないと判定している。篩をかける前は、全てが素数である(False)と考えている
探索したい最大の数(n_ini)に対して、分割単位(dn)がきちんと割り切れる状況を考えている。つまり、n_ini/dnが整数で、bがゼロである。bが0でなかったときの処理は実装していない。
このプログラムに、バグが残っていないと保証できない(一応、他のサイトと結果を比較してずれてはいないことを確認)。

結果

10億までの数に対して、素数を求めるのにかかった時間は80秒(1分20秒)。

このプログラムで、仮に10兆まで求めるとしたら、80秒×1万で、約9日程度かかる見積もり。

速くするには

速いプログラムは10億までの素数の探索に10秒切るから、お世辞にも早いとはいえない。

より速くするには以下のような工夫が挙げられる。

分割単位を切りのいい数字にする。

上のプログラムは、分割単位dnは、適当な数字にしても動く。
だが、その分、プログラム内部で、余計な処理が加わっている。
分割単位を2×3×5×7×11×13×17などにすれば、もう少し処理の負担が落ちるはず。

覚えておく素数を減らす

このプログラムは、最後まで、素数リストに素数を記録しているが、計算に必要な素数は10億の平方根の31622までで十分。それ以降の素数は順次、出力した方がいい。メモリという観点からも、より大きな数字を扱う場合には、この工夫が必須になる。

実行速度最強？と言われているC言語で実装。

C#よりもC言語の方が速いと思う。C言語の方がより機械側に近い言語ゆえに。

より大きな数字を扱うには(10兆を目指して)

まず、出力した結果の容量がバカにならない。

10億までの容量は、975MB。

975MBには、素数が「何」番目かという情報も含まれている。

素数だけ挙げていくのであれば、容量はおよそ半分の500MBぐらいに落ち着くはず。

10兆までの素数を挙げるチャレンジが色々な記事で行われているが、出力結果を圧縮しないと5Tぐらいになってしまいそうだ。

パソコンの容量的に、どう考えても5Tは厳しい。

あと、出力結果は、5T分をまるまる保存するわけにはいかず、ある程度分割していくことを考えないといけない。

10億までの結果である975MB (約1GB)分のテキストファイルは、TeraPadやWindows付属のメモ帳で開くことができなかった。

※メモリ不足とTeraPadには警告された。おそらく、テキストファイルの容量と同じオーダーのメモリを確保しようとして失敗したのだろう。

※フリーソフトの「Giga Text Viewer」(大容量のテキストファイルを開くのに特化したテキストエディタ)を使って開くことはできた。

このような事態を避けるためにも、結果の出力はある程度こまめに行った方がいいのかもしれない。

単純にエラトスネスの篩のプログラムを実装した時の記事

エラトステネスの篩の素数判定プログラム(c#)

～ギャンブルに絶対儲かる必勝法があるのだろうか？～

私(サイト主)はこの疑問に対して非常に興味を持ち、プログラミングで検証してみました。

このサイトを応援してもいいかなと思う人はぜひとも購入を検討してみてください。

ギャンブルの必勝法が本当に儲かるかプログラミングで検証してみた

おおきな数字に対して、素数リストを作るためのプログラム

はじめに

プログラムのアルゴリズム

プログラム

注意点

結果

速くするには

より大きな数字を扱うには(10兆を目指して)

関連記事

コメントを残すコメントをキャンセル

検索

書籍一覧

スポンサーリンク

おすすめ記事

はじめに

プログラムのアルゴリズム

プログラム

注意点

結果

速くするには

より大きな数字を扱うには(10兆を目指して)

関連記事

コメントを残す コメントをキャンセル

検索

書籍一覧

スポンサーリンク

おすすめ記事

コメントを残すコメントをキャンセル