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

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

Написал алгоритм, похожий на решето Эратосфена. За 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 = %in", 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-битных расстояний.

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

Автор: NuShaman

Источник