Что такое простые числа, для тех кто не знает поясняю.
Простое число это такое положительное число, которое делиться только на себя и на единицу.
Примеры простых чисел до 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Существует алгоритм нахождения простых чисел предложенный Эратосфеном (275-194 до н.э., Греция), который разработал ‘сито’, чтобы найти простые числа.
Сито, как фильтр, который используется для фильтрации всех чисел, в результате чего остаються только простые числа.
По методу решета Эратосфена, чтобы найти простые числа до 100, нужно сделать схему натуральных чисел. Возьмем на примере числа от 1 до 100:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Шаг 1. Нужно вычеркнуть все числа кратные 2, т.е. каждое 2 число начиная с 4.
Шаг 2. Нужно вычеркнуть все числа кратные 3, т.е. каждое третье число начиная с 3. Возможно некоторые числа уже будут вычеркнуты, такие как например 6, т.к. оно было кратно 2.
Кажый 4 вычеркивать не нужно, т.к. мы их уже вычеркнули когда вычеркивали 2.
Шаг 3. Далее нужно вычеркнуть все числа кратные 5, т.е. каждое пятое число начиная с 5. Возможно некоторые числа уже будут вычеркнуты, как и в прошлом случае.
Нужно продолжать это делать, пока все номера до 100 не будут вычеркнуты.
Таким образом оставшиеся номера и будут простыми числами.
Ниже приведена таблица простых чисел от 2 до 10000 (1229 штук). Единица не включена, извините. Некоторые считают, что единица не включена поскольку. она и не может там быть. "Простым числом называются числа имеющие два делителя: единицу и само число." А число 1 имеет только один делитель, оно не относится ни к простым, ни к составным числам. (толковое замечание от Ольги 21.09.12) Мы, тем не менее помним, что простые числа вводятся иногда и так: "Простым числом называются числа которые делятся нацело на единицу и само себя." В этом случае единица, очевидно, является простым числом.
Таблица простых чисел от 2 до 1000. Таблица простых чисел от 2 до 1000 выделена серым.
Давеча снова увлекся простыми числами. Манит меня их тайна.
Написал алгоритм, похожий на решето Эратосфена. За 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-битных расстояний.
Хотя в наш век Гигабайтных емкостей это не сильно принципиально.
Загрузка...
