База данных простых чисел

Давеча снова увлекся простыми числами. Манит меня их тайна.

Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.

Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!

Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?

Пришла в голову идея записывать в файл не сами числа, а расстояния между ними. А расстояние между соседними простыми числами всегда должно быть небольшим, предположил, что уместится в один байт.

Осталось узнать максимально-возможное расстояние для определенного диапазона чисел. Поскольку разница между простыми числами всегда есть четное число (кроме расстояния между 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 — максимально-возможное расстояние по простое число значением до 1 миллиарда.

Написал код записи в файл:

FILE* fd; fd = fopen("primes.bin", "w+"); unsigned char b1[1]; b1[0] = Rast; fwrite(b1,1,1,fd); fclose(fd); 

Запустил до 300 миллионов:

./primes 1 300000000

В файле primes.bin получил 16 миллионов первых простых чисел. Сжал архиватором 7-Zip, файл ужался до 9 Мб.

P.S. Есть идея, как еще сильнее сжать БД простых чисел. Надо простые числа разделить на 4 группы по последней десятичной цифре: 1, 3, 7, 9. Расстояние между числами делить на 10. Так же сформировать 4 файла. При этом возможно, что для значений расстояния можно будет отвести не 8 бит, а меньше, тогда придется реализовать формирование байтового буфера из, например, 5-битных расстояний.

Хотя в наш век Гигабайтных емкостей это не сильно принципиально.