エラトステネスのふるいに似たアルゴリズムを書きました。 3時間にわたって、プログラムは70万個の最初の素数を見つけました。 そして、それらを掛け合わせて1億個に相当する小数桁数の数を得るには、少なくとも1400万個の素数が必要です。
Bodigrimのユーザーが書いた記事「もう一度素数の検索について」から、 Atkin Sieveを使用して機能する素早いプログラムprimegenの存在について学びました。 LUbuntu仮想マシン（VirtualBox）にインストールしました。 実際、 primegenは非常に高速です！
その後、1400万の素数をどのように節約するかという疑問が生じました。 単純に各素数をint32としてファイルに書き込むことができます。 また、素数が32ビットの累乗より大きい場合はどうなりますか？
数字そのものではなく、それらの間の距離をファイルに書き込むことが私には起こりました。 また、隣接する素数間の距離は常に小さくする必要があり、1バイトに収まることが示唆されます。
特定の範囲の数値に対して可能な最大距離を見つけることは残っています。 素数の差は常に偶数であるため（2と3の間の距離を除く）、距離を2で除算します。
primegenプログラムでは、ソースファイルprimes.cで、画面に数字を表示する代わりに、数字間の距離の数に関する統計を計算するアルゴリズムを実装しました。
int RastCount_Index = 0; int RastCount[1000]; for(i=0;i < 1000; i++) RastCount[i] = 0; for (;;) { u = primegen_next(&pg) - p; p += u; if (p > high) break; for (i = 0;u;++i) { u += digits[i]; if (u >= 200) { digits[i] = u % 10; u = u / 10; } else { digits[i] = mod10[u]; u = div10[u]; } } if (i > len) len = i; int LetsRast, index; LetsRast = 0; index = 0; char r[40], r_old[40]; for (i = 0;i < 40; i++) { r[i] = 0; r_old[i] = 0; } for (i = len - 1;i >= 0;--i) { if (! LetsRast) if (digits_old[i] != digits[i]) LetsRast = 1; if (LetsRast) { r[index] = '0' + digits[i]; r_old[index] = '0' + digits_old[i]; index++; } } int ri, ri_old, Rast; ri = atoi(r); ri_old = atoi(r_old); Rast = (ri - ri_old) >> 1; RastCount[Rast]++; if (Rast > RastCount_Index) RastCount_Index = Rast; for (i = len-1;i >= 0; i--) digits_old[i] = digits[i]; } for(i = 0; i <= RastCount_Index; i++) printf("%i = %i\n", i, RastCount[i]);
ターミナルで、次を実行します。
./primes 1 1000000000
10秒後、リストが表示されます。
0 = 1（数字2と3の間の距離）
1 = 3424507
...
141 = 1
したがって、141は最大10億までの最大素数距離です。
ファイルに書き込むコードを書きました：
FILE* fd; fd = fopen("primes.bin", "w+"); unsigned char b1[1]; b1[0] = Rast; fwrite(b1,1,1,fd); fclose(fd);
最大3億台を発売：
./primes 1 300000000
このファイルでは、primes.binが1600万個の最初の素数を受け取りました。 アーカイバ7-Zipによって圧縮され、ファイルは9 MBに縮小されました。
PS素数のデータベースをさらに強力に圧縮する方法はあります。 素数を最後の10進数字に従って4つのグループに分割する必要があります：1、3、7、9。数字間の距離を10で割ります。また、4つのファイルを作成します。 同時に、8ビット未満を距離値に割り当てることができますが、5ビット距離などからバイトバッファーの形成を実装する必要があります。
ギガバイトの容量の時代ではありますが、これはそれほど重要ではありません。