Таблица простых чисел до 1000000

Таблица простых чисел до 1000000

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

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

Читайте также:  Музыкальный центр technics авито россия

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

Таблица простых чисел от 1 до 10000. Таблица простых чисел от 1 до 1000

Ниже приведена таблица простых чисел от 2 до 10000 (1229 штук). Единица не включена, извините. Некоторые считают, что единица не включена поскольку. она и не может там быть. "Простым числом называются числа имеющие два делителя: единицу и само число." А число 1 имеет только один делитель, оно не относится ни к простым, ни к составным числам. (толковое замечание от Ольги 21.09.12) Мы, тем не менее помним, что простые числа вводятся иногда и так: "Простым числом называются числа которые делятся нацело на единицу и само себя." В этом случае единица, очевидно, является простым числом.

Таблица простых чисел от 2 до 1000. Таблица простых чисел от 2 до 1000 выделена серым.

Простые числа — это целые натуральные (положительные) числа больше единицы, которые имеют ровно 2 натуральных делителя (только 1 и самого себя), т.е. не делится ни на одно другое число, кроме самого себя и единицы. Все остальные числа кроме единицы называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные.

  • Подробнее о простых числах сможете узнать в видео уроке "Простые и составные числа"

Последовательность простых чисел начинается так (от 2 до 10000 их 1229):

Ссылка на основную публикацию
Сканер ricoh sp 220snw
Компания Ricoh — далеко не новичок на рынке печатающих устройств. Это глобальная корпорация со штаб-квартирой в Токио и представительствами во...
При каком альфа векторы компланарны
Единого обозначения компланарность не имеет. Свойства компланарности Пусть — векторы пространства . Тогда верны следующие утверждения: Если хотя бы один...
При каком значении m прямая параллельна плоскости
Точка C(—3, 4,1) найдена. 6. Написать уравнение плоскости, проходящей через точки M1(1, —2, 1), M2(4, 2, 3) и параллельной вектору...
Сколько дают на ютубе за 1000 просмотров
Многих пользователей YouTube, а также начинающих видеоблогеров справедливо интересует вопрос: «А сколько YouTube платит за тысячу или миллион просмотров?» Если...
Adblock detector