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

Нещодавно знову захопився простими числами. Манить мене їх таємниця.

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

Зі статті «Ще раз про пошук простих чисел», написаної користувачем Bodigrim, дізнався про існування швидкої програми primegen, яка працює використовуючи решето Аткіна. Встановив її у віртуальній машині LUbuntu (VirtualBox). Дійсно, primegen дуже швидко працює!

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

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

Залишилося дізнатися максимально-можливу відстань для певного діапазону чисел. Оскільки різниця між простими числами завжди є парне число (крім відстані між 2 і 3), то розділимо на відстань 2.

У програмі primegen у вихідному файлі простих чисел.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]);


У терміналі виконав:

./простих 1 1000000000

Через 10 секунд відобразився список:
0 = 1 (відстань між числами 2 і 3)
1 = 3424507

141 = 1
Таким чином, 141 — максимально-можливу відстань по просте число значенням до 1 мільярда.

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

FILE* fd;
fd = fopen("простих чисел.bin", "w+");
unsigned char b1[1];
b1[0] = Rast;
fwrite(b1,1,1,fd);
fclose(fd);

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

./простих 1 300000000

У файлі простих чисел.bin отримав 16 мільйонів перших простих чисел. Стиснув архіватора 7-Zip файл стиснувся до 9 Мб.

p.s. Є ідея, як ще сильніше стиснути БД простих чисел. Треба прості числа розділити на 4 групи за останньою десятковій цифрі: 1, 3, 7, 9. Відстань між числами ділити на 10. Так само сформувати 4 файлу. При цьому можливо, що для значень відстані можна буде відвести не 8 біт, а менше, тоді доведеться реалізувати формування байтового буфера з, наприклад, 5-бітних відстаней.

Хоча в наш вік Гігабайтних ємностей це не дуже принципово.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.