[Из песочницы] База данных простых чисел
Давеча снова увлекся простыми числами. Манит меня их тайна.Написал алгоритм, похожий на решето Эратосфена. За 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®; 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-битных расстояний.
Хотя в наш век Гигабайтных емкостей это не сильно принципиально.
