РЕШЕТО ПОПИКА И ТЕСТ ПРОСТОТЫ НА ЕГО ОСНОВЕ

POPIK SIEVE AND TEST FOR DETERMINATION OF PRIMALITY

Pavel Popik

Radio engineer,

Russia, St. Petersburg

АННОТАЦИЯ

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

ABSTRACT

This article contents the data based on the results of the statistical study about the sieve which allows to find prime numbers within the set interval as well as the test for determination of primality of the certain number based on the operating model of the sieve. The functionality of the sieve and the test for determination of primality are based on fundamental distinctions between prime and composite numbers. Prime numbers have the only one denominator, but composite numbers have not less than two denominators. There can be found comparative characteristics for three known methods of sieve implementation as well as examples of segmentation of a new sieve and new recurrent search of prime numbers on the basis of the presented operating model.

Ключевые слова: решето Эратосфена; решето Аткина; решето Сундарама; простые числа; составные числа; истинный тест простоты; основная теорема арифметики; вычислительная модель; горизонтальное сегментирование решета; вертикальное сегментирование решета.

Keywords: Erastosthene sieve; Atkin sieve; Sundaram sieve; prime numbers; composite numbers; good test for determination of primality; fundamental theorem of arithmetic; computational model; horizontal segmentation of sieve; vertical segmentation of sieve.

Введение.

Во многих публикациях утверждается, что простые числа (ПЧ) отличаются от составных тем, что они без остатка могут делиться только на единицу или на самих себя. Соответственно, любое составное число, как утверждает основная теорема арифметики, может однозначно быть представлено произведением энного числа простых чисел, делителей, на которые оно делится без остатка. Но поскольку единицу доказуемо не принято считать простым числом, то в первом утверждении заключено противоречие. Как деление любого числа на единицу, так и деление ПЧ на единицу, несет в себе бессмыслицу. Делить на единицу, значит ничего не делить. ПЧ при таком условии оказываются составными. Аналогичное противоречие заключено в делении ПЧ самого на себя. Это противоречие может частично сниматься при делении достаточно большого ПЧ машинным способом на такое же большое число, когда визуально не удается сразу обнаружить сходство, и результат будет свидетельствовать об их полном равенстве. Вывод из этого рассуждения напрашивается о том, что это вопрос не математики, а, скорее, философии.

Представляемое новое решето, основанное на алгоритме фильтрации, имеет много общее с другими способами просеивания натуральных чисел (НЧ), так как для определения принадлежности числа к простому или составному всегда выполняются операции деления и отбора по критерию. Для предлагаемого решета критерием простоты является наличие одного делителя, равного самому себе, либо его отсутствие. А для составного числа критерием отбора служит наличие хотя бы одного делителя, но отличного от самого числа, то есть меньшего самого числа.

Краткий обзор трех алгоритмов просеивания

Исторически первым принято считать решето Эратосфена. Алгоритм просеивания по нему оперирует с неким непрерывным массивом, начинающимся с двух и до границы, в пределах которой нужно отыскать простые числа. Задача найти все простые в другом массиве, опираясь на уже известные простые числа в нем не ставится. Использовать сам алгоритм в качестве теста простоты также не представляется возможным, особенно для очень больших чисел, для которых отсутствуют списки ПЧ в том же диапазоне величин. Кроме того, с возрастанием размера массива почти геометрически возрастает сложность и объем необходимой памяти. Думается, Эратосфен не ставил перед собой задачу разрешения всех этих сложностей.

На этапе развития ЭВМ, когда объемы запоминающих устройств существенно отставали от скорости вычислений, для поиска ПЧ с ограниченными ресурсами памяти был разработан нетривиальный алгоритм, названный решетом Аткина. Алгоритм достаточно сложный и для упрощения вычислений использует предпросеивание и сегментацию [Л1]. С учетом многократно возросших вычислительных возможностей и удовлетворения технологических потребностей, связанных с ПЧ (в криптографии), представляется, что тест Аткина постепенно уходит в историю. Об этом в настоящее время свидетельствуют примеры распределения ресурсов и вычислительных мощностей в сети интернет.

Внешне несколько проще выглядит алгоритм родом из тридцатых годов двадцатого века под названием решето Сундарама, который разработал индийский студент. Он также оперирует с неким массивом и опирается на известные свойства составных чисел. Как и в двух предыдущих алгоритмах для просеивания в решете используется операция исключения составных чисел из списка. Актуальность его сегодня представляется лишь в том, что он существенно отличается от двух предыдущих.

Описание вычислительного эксперимента

Моделирование для исследования процесса просеивания натуральных чисел проводилось в офисном приложении Excel. Из источника в интернете использовалась последовательность ПЧ, необходимая для поиска критериев просеивания НЧ [Л3]. В левом столбце был сформирован возрастающий перечень нечетных чисел в пределах до 60 тысяч (30 000 чисел). Затем в следующем столбце каждому нечетному числу был присвоен знак «р», если число является простым, для того чтобы визуально контролировать результат работы решета. У составных чисел ячейка справа оставалась пустой. Эта операция присвоения статуса была выполнена при помощи функции «СЧЕТЕСЛИ» по массиву известных ПЧ. В первой строке вычислительной модели (ВМ) расположились по возрастанию ПЧ от 3 до 199, которые  при вычислениях будут делителями. Весь массив ячеек для вычислений от 3 до 199 по горизонтали и от 3 до 30 000 по вертикали был заполнен одной и той же формулой «ЕСЛИ($C106/E$1=ОКРУГЛ($C106/E$1;0);1;"")», которая проверяет результат целочисленного деления конкретного нечетного числа на делитель из первой строки. При выполнении условия в ячейке появляется единица. В крайнем правом столбце построчно суммировалось количество делителей для каждого нечетного числа. Затем на столбец с суммами делителей был установлен фильтр, который позволяет отсеивать по выбранным критериям соответствующие группы нечетных чисел. На этом построение ВМ было завершено.

Алгоритм работы решета

В результате вычислений для фильтрации было представлено семь критериев: суммы от 0 до 5; и пустые ячейки, которые образуются после окончания списка суммирования. Фильтрация по критерию один делитель показала, что в нее в начале списка, кроме составных чисел, вошли все ПЧ из первой строки делителей и далее только составные числа. Отбору уже известных ПЧ по этому критерию мешают в нашем алгоритме числа, представляющие степень (>=2) ПЧ. Но эти ПЧ нам и не требуется селектировать в силу их известности. Селекция по критерию 0 выдала перечень ПЧ до некоего предела, после которого начали по статусу «р» или «не р» встречаться составные числа. Их количество росло по мере приближения к концу вычислительной матрицы. Первым в списке ПЧ оказалось следующее по списку после 199 число 211. А первым составным в списке фильтрации оказалось число, равное квадрату 211. Таким образом, вырисовались границы диапазона для предлагаемого алгоритма решета. Между 199 и квадратом 211. Логика алгоритма становится очевидной, поскольку после 199 ни одно ПЧ не имеет делителя, а начиная с 211 ни одно составное число, имеющее в качестве минимального делителя 211, не может быть меньше квадрата 211. Границы диапазона селекции были проверены для других начальных условий алгоритма решета с меньшим числом делителей. Полученные результаты представлены в таблице 1.

Таблица 1.

Таблица расширения диапазона просеивания и числа найденных ПЧ

Первый столбец показывает максимальный из делителей, второй - число отфильтрованных нулей (чем меньше нулей, тем большее количество составных чисел отфильтровано). В третьем столбце значение составного числа, где найден первый ноль, в четвертом – корень квадратный из этого числа. Пятый столбец совпадает с четвертым, так как в нем указано следующее за максимальным ПЧ из массива известных ПЧ. Это и есть подтверждение верхней границы алгоритма. Шестой - ближайшее ПЧ к первому нулевому составному (С). В последнем столбце виден рост числа найденых ПЧ при росте числа ПЧ-делителей.

Несколько слов о скорости работы алгоритма решета, для ее увеличения при программной реализации поиск делителей стоит прекращать после нахождения первого из них, и переходить к следующему нечетному числу. В построенной для эксперимента ВМ это также реализуемо, но приведет к усложнению модели и снижению скорости вычислений.

Горизонтальное сегментирование решета

Название сегментирования чисто условное, так как вычислительная матрица в первоначальной модели ориентирована в соответствии с параметрами электронной таблицы. В ней число строк (1048576) на несколько порядков превышает число столбцов (16384), и разместить 30000 нечетных чисел по строкам не совсем оправдано. Как и в решете Аткина, проводить поиск ПЧ по блокам в пределах определенных заранее границ при нехватке вычислительных ресурсов вполне очевидно [Л1].

Вертикальное сегментирование решета

С вертикальным сегментированием несколько сложнее, но в сравнении с горизонтальной сегментацией существенно сокращается объем вычислений. Все делители разбиваются на группы и вся вычислительная матрица вместе с ними. Число и размер групп произвольный и может разбиваться вплоть до каждого отдельного делителя, когда число ПЧ равно числу групп. При этом, за счет того, что в предыдущей группе первые ПЧ уже достоверно установлены, во второй группе их проверять нет смысла. Вычисления во второй группе начинаются со строки, где расположен первый ноль для составного числа. Для третьей слева группы и далее аналогично до последней удаляются формулы из уже достоверно установленных ячеек (где ПЧ, а где составное число). Суммы делителей для каждого нечетного числа после завершения вычислений во всех вертикальных группах также суммируются и показывают итоговый результат просеивания для всего диапазона работы решета. На двух ВМ было выполнено просеивание для одного и того же итогового диапазона и количества делителей. В одной ВМ просеивание выполнялось без вертикального сегментирования, а в другой с разбивкой на 5 вертикальных групп по 5 делителей на каждую. Параметры вычислительной матрицы от 3 до 101 (25 делителей) и 20000 нечетных чисел (3 – 40001). Результаты просеивания оказались идентичными при сравнении с рядом известных ПЧ. Но ряд ПЧ в первой ВМ начинался со 103 (26-е ПЧ), а в сегментированной ВМ с ПЧ первого сегмента, т.е. с 17 так как каждый из сегментов вносил свои начальные ПЧ в общий список. Фрагмент результата сравнения показан на рисунке 1.

Рисунок 1. Результаты сравнения решета с сегментированием и без

Вариант вертикального сегментирования для решета Эратосфена, когда число групп (сегментов) равно числу ПЧ-делителей, описан в Википедии [Л2]. Там начало вертикального сегмента для ПЧ также начинается с составного числа, равного его квадрату. Описанная выше ВМ вертикального сегментирования представлена в облачном хранилище [Л4]. Ячейки с удаленными формулами выделены заливкой серым узором.

Рекуррентный алгоритм поиска ПЧ на основе решета

Алгоритм решета работает от самых истоков, когда мы ничего не знаем о ПЧ. Обнаруживаем первого кандидата на ПЧ число 2. Начинаем просеивание, следующее за 2 число три также делится только на само себя. Оно определяет верхнюю границу диапазона первого просеивания, равную 9. Четыре делится на 2,  пока у нас лишь один делитель. Пять не делится на 2, шесть делится на 2, семь не делится, восемь делится. Итого получаем 3 ПЧ (3, 5, 7). На втором рекуррентном шаге у нас четыре ПЧ. Просеиваем, первое, что не делится не на один из делителей первого шага, это 11. Его квадрат 121. До него находим еще 26 ПЧ (включая 11). Последнее в списке 113, делаем третий шаг уже с 30 ПЧ-делителями. За 113 следует ПЧ равное 127, его квадрат равен 16129. До него получаем еще 1847 ПЧ, последнее ПЧ в списке 16127, следующее за ним 16139. Итого в списке за 4 шага просеивания 1847 ПЧ. Квадрат 16139 равен 260 467 321. Такое количество ПЧ отсеять уже не под силу офисному приложению Excel. Напоминает цепную реакцию распада урана. Этот рекуррентный алгоритм может сэкономить немного памяти, например, для теста простоты. Если начинать с третьего шага, для которого необходимо постоянно хранить всего 30 ПЧ, то после вычисления четвертого шага получаем 1847 ПЧ. Этого должно быть достаточно для тестирования на простоту ПЧ вплоть до десятка миллионов ПЧ.

Для теста простоты, который основан на том же алгоритме, нет смысла посвящать целый раздел статьи. Если число N находится в проделах

P_i < N < (P_i+1)²;                                                                      (1)

где P_i – максимальный из ПЧ-делителей, то для ПЧ делителей нет, а для составных чисел оно больше нуля. При помощи него легко находятся доказательство простоты числа Мерсенна М₃₁ и ближайшее ПЧ к вышеприведенному числу 260 467 321, оно равно 260 467 313.

Заключение

Необходимо сравнить предлагаемое решето с наиболее близким аналогом, которым является решето Эратосфена (РЭ). Известно, что все натуральные числа подразделяются на две категории: простые и составные. Составные однозначно могут быть представлены в виде произведения простых, а ПЧ служат своего рода системой координат для них и ни на что не делятся. Поэтому по определению для установления простоты числа его необходимо проверить на целочисленную делимость на все предыдущие ПЧ, своеобразная рекуррентная зависимость. Алгоритм решета Эратосфена состоит из трех шагов: а) деления на меньшее ПЧ, б) оценки результата по критерию целочисленного деления и в) фиксации результата, в случае делимости в форме вычеркивания. На этом сходство заканчивается, существенных различий несколько. Основное различие решета Эратосфена от нового решета заключается в том, что оно просеивает простые числа в интервале от 2 до N, которое больше либо равно P_i. А новое решето просеивает простые числа в интервале от N до квадрата P_i+1. РЭ обнаруживает ПЧ начиная с 2, а НР необходимы хотя бы одно известное ранее ПЧ  в качестве делителя. Для этого достаточно даже одной двойки, как отмечено в предыдущем разделе. Кроме того, необходимо обратить внимание на следующее:

1). После первого выполнения РЭ на интервале 2 - N алгоритм уходит в историю, так как все ПЧ становятся известны и больше алгоритм не нужен. В нем последовательность «деление» - оценка и фиксация результата совмещены в одну последовательность для каждого НЧ. Для другого М (большего N) надо все проделать сначала, начиная с М - N. Это вариант горизонтального сегментирования в РЭ. Новое решето (НР) разрывает эту последовательность, оценка результата и фиксация его откладываются до завершения алгоритма. Между делением и оценкой вклинивается операция суммирования полученного количества делителей. За счет дополнительной операции суммирования алгоритм оказывается более технологичным.

2). Задача поиска ПЧ на произвольном интервале для РЭ снижает эффективность алгоритма. Так при поиске ПЧ в пределах до ста, опираясь на четыре первых ПЧ, мы игнорируем еще 5 ПЧ между 100 и 121, которые легко устанавливаются новым решетом. А, зная первые 30 ПЧ, и, просеивая ПЧ до 1000, мы игнорируем уже 1709 ПЧ между 1000 и 16129 (смотрите предыдущий раздел). То есть, постановка задачи для РЭ о поиске ПЧ на произвольном промежутке представляется некорректной. В НР установлена точная граница области ПЧ выражением (1).

3) Использование большого списка уже известных ПЧ перед РЭ, думается,  не предполагалось в силу исторических причин, важно было на основе алгоритма дать определение, что такое ПЧ и как их определить. А, имея, например, миллион ПЧ, для оценки простоты некоего числа из этого интервала ничего делить не надо, достаточно путем поиска установить его отсутствие в списке этих ПЧ. Что значительно проще.

4) Благодаря наличию у сегодняшнего исследователя такого мощного инструмента, как компьютер, можно с помощью более простого НР легко отфильтровать (просеять) миллионы ПЧ за разумно короткое время, в том числе применяя два вида сегментации. Тест простоты благодаря определенным четким границам обладает невиданными возможностями, которые отражены в разделе  рекуррентного алгоритма. Он предназначен преимущественно для электронных таблиц, таких как Excel, но может быть использован и в программном варианте.

5) В противоположность решету Аткина НР требует больше памяти относительно РЭ, который находится по балансу память-вычислительный ресурс примерно между ними. Наблюдается своеобразный обмен - проигрыш в памяти на выигрыш в скорости вычислений и технологичность. Под технологичностью в создании ВМ понимается процесс, который путем всего десяти нажатий на клавиши позволяет заполнить простой вышеприведенной формулой, использованной в вычислительной модели, весь массив для вычислений.

В качестве примера НР в списке литературы [Л5] представлен пример горизонтального сегментирования для просеивания ПЧ вплоть до НЧ 5004169. Размер сегмента 330 столбцов на 6144 строки. Просеивались НЧ с 4000303 до 4344377, найдено 22561 ПЧ. В среднем просеивалось 777 ПЧ за один цикл алгоритма, состоящего из трех шагов. Итоговый размер файла всего 17082 Кб.

Список литературы:

1. Алгоритмы поиска простых чисел. https://temofeev.ru/info/articles/algoritmy-poiska-prostykh-chisel/
2. Википедия. Решето Эратосфена. https://ru.wikipedia.org/wiki/Решето_Эратосфена
3. Справочник простых чисел. http://www.unconnected.info/sn100.aspx
4. Ссылка на ВМ вертикального сегментирования. https://disk.yandex.ru/i/GBEciP0oqgc1-Q
5. Ссылка на ВМ горизонтального сегментирования. https://disk.yandex.ru/i/M_seidKreRNKGA