Давеча снова увлекся простыми числами. Манит меня их тайна.
Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.
Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!
Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?
Пришла в голову идея записывать в файл не сами числа, а расстояния между ними. А расстояние между соседними простыми числами всегда должно быть небольшим, предположил, что уместится в один байт.
Осталось узнать максимально-возможное расстояние для определенного диапазона чисел. Поскольку разница между простыми числами всегда есть четное число (кроме расстояния между 2 и 3), то разделим расстояние на 2.
В программе primegen в исходном файле primes.c вместо вывода числа на экран реализовал алгоритм подсчета статистики по кол-ву расстояний между числами:
В терминале выполнил:
Через 10 секунд отобразился список:
0 = 1 (расстояние между числами 2 и 3)
1 = 3424507
…
141 = 1
Таким образом, 141 — максимально-возможное расстояние по простое число значением до 1 миллиарда.
Написал код записи в файл:
Запустил до 300 миллионов:
В файле primes.bin получил 16 миллионов первых простых чисел. Сжал архиватором 7-Zip, файл ужался до 9 Мб.
P.S. Есть идея, как еще сильнее сжать БД простых чисел. Надо простые числа разделить на 4 группы по последней десятичной цифре: 1, 3, 7, 9. Расстояние между числами делить на 10. Так же сформировать 4 файла. При этом возможно, что для значений расстояния можно будет отвести не 8 бит, а меньше, тогда придется реализовать формирование байтового буфера из, например, 5-битных расстояний.
Хотя в наш век Гигабайтных емкостей это не сильно принципиально.
Таблица простых чисел от 1 до 10000. Таблица простых чисел от 1 до 1000
Ниже приведена таблица простых чисел от 2 до 10000 (1229 штук). Единица не включена, извините. Некоторые считают, что единица не включена поскольку. она и не может там быть. "Простым числом называются числа имеющие два делителя: единицу и само число." А число 1 имеет только один делитель, оно не относится ни к простым, ни к составным числам. (толковое замечание от Ольги 21.09.12) Мы, тем не менее помним, что простые числа вводятся иногда и так: "Простым числом называются числа которые делятся нацело на единицу и само себя." В этом случае единица, очевидно, является простым числом.
Таблица простых чисел от 2 до 1000. Таблица простых чисел от 2 до 1000 выделена серым.
Ниже приведена таблица простых чисел от 2 до 10000 (1229 штук). Единица не включена, извините. Некоторые считают, что единица не включена поскольку. она и не может там быть. "Простым числом называются числа имеющие два делителя: единицу и само число." А число 1 имеет только один делитель, оно не относится ни к простым, ни к составным числам. (толковое замечание от Ольги 21.09.12) Мы, тем не менее помним, что простые числа вводятся иногда и так: "Простым числом называются числа которые делятся нацело на единицу и само себя." В этом случае единица, очевидно, является простым числом.
Таблица простых чисел от 2 до 1000. Таблица простых чисел от 2 до 1000 выделена серым.
Загрузка...
