АЛЬТЕРНАТИВНЫЙ ДЕТЕРМИНИРОВАННЫЙ АЛГОРИТМ ПОИСКА НЕЧЕТНЫХ ПРОСТЫХ ЧИСЕЛ

​AN ALTERNATIVE DETERMINISTIC ALGORITHM FOR SEARCHING ODD PRIMES

Alexander Yutkin

Teacher, Volga State College»,

Russia, Samara

АННОТАЦИЯ

Рассматривается альтернативный детерминированный алгоритм поиска нечетных простых чисел до заданного числа N. Идея алгоритма состоит в исключении из последовательности нечетных натуральных чисел составных чисел вида:  Приводится псевдокод данного алгоритма, рассматриваются вопросы его вычислительной сложности и быстродействия в сравнении с уже известными алгоритмами Эратосфена и Сундарама.

ABSTRACT

An alternative deterministic algorithm for finding odd primes up to a given number N is considered. The idea of the algorithm is to exclude composite numbers of the form from the sequence of odd numbers. The pseudocode of this algorithm is given and the issues of its performance and computational complexity are considered in comparison with the well-known algorithms of Eratosthenes and Sundaram.

Ключевые слова: простые числа, составные числа, алгоритм поиска, разность квадратов натуральных чисел.

Keywords: primes, composite numbers, search algorithm, difference of squares of natural numbers.

Введение

Простые числа в математике имеют фундаментальное значение, поэтому проблема поиска простых чисел была и остается актуальной по сей день.

В настоящее время существует не так много концептуально различных детерминированных алгоритмов поиска простых чисел до некоторого натурального числа N. Наиболее известные из них, отличающиеся своей простотой и одновременно высокой эффективностью: решето Эратосфена [1] и решето Сундарама [2]. Самый популярный и востребованный алгоритм Эратосфена основан на исключении из ряда натуральных чисел составных чисел, кратных уже найденным простым. Менее распространенный алгоритм Сундарама использует идею, которая состоит в исключении из ряда нечетных чисел составных чисел вида , где . Несмотря на разные подходы к просеиванию простых чисел, оба алгоритма имеют высокую производительность.

Существуют ли иные (альтернативные) способы поиска простых чисел, настолько же простые и эффективные как указанные?

В работе рассматривается альтернативный детерминированный алгоритм поиска нечетных простых чисел до некоторого натурального числа N (далее – альтернативный алгоритм) на основе использования следующей теоремы: каждое нечетное простое число представимо в виде разности двух квадратов натуральных чисел и притом только одним способом (далее – терема).

Из теоремы следует, что натуральное число, допускающее более, чем одно разложение на разность двух квадратов натуральных чисел является составным. Доказательство теоремы приводится В. Серпинским [3, С. 57-58].

Альтернативный алгоритм поиска нечетных простых чисел

Для наглядности построим таблицу разностей квадратов натуральных чисел: .

Сделаем несколько пояснений.

1. Используемая теорема содержит необходимые, но недостаточные условия простоты числа: не только простые числа, но и квадраты нечетных простых чисел (9, 25, 49, …) представимы в виде разности двух квадратов натуральных чисел единственным способом. Для учета таких случаев полагаем, что  может принимать нулевые значения.

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

3. Поскольку все четные числа за исключением 2 являются составными, целесообразно исключить из рассмотрения все четные значения . Им соответствуют пустые ячейки в правой части таблицы относительно главной диагонали (рис. 1).

Рисунок 1. Фрагмент таблицы разности квадратов натуральных чисел

Числа вида  при  имеют разложение на тривиальные множители:  и образуют множество нечетных чисел, в том числе нечетных простых чисел (для них это разложение единственное). Последовательность нечетных чисел располагается на главной диагонали таблицы (рис. 1).

Числа вида  при  имеют разложение на множители:  делители числа c, причем

 Согласно следствию из теоремы числа вида c образуют множество нечетных составных чисел, которые располагаются в ячейках таблицы вне главной диагонали (рис. 1). Таким образом, множество нечетных простых чисел может быть представлено как исключение из множества нечетных чисел множества составных чисел вида .

Для поиска нечетных простых чисел до заданного числа N требуется исключить из последовательности нечетных чисел, меньших или равных заданному N, составные числа вида  для всех таких, что  

С учетом вышеизложенного, альтернативный алгоритм поиска нечетных простых чисел можно представить в виде следующей последовательности шагов:

1. Сформировать массив из нечетных чисел от 3 до N.

2. Переменной  присвоить значение первого нечетного числа:  переменной  присвоить значение .

3. Если соблюдается условие: , выполнить шаг 4, иначе завершить исполнение алгоритма (для значений таких, что  проверить условие: ).

4. Пока выполняется условие: , исключать из массива нечетных чисел элементы, принимающие значения , увеличивая значения переменных  на единицу после каждой итерации ().

5. Переменной  присвоить значение следующего нечетного числа:

 переменной  присвоить значение .

6. Повторить шаг 3.

По завершению работы алгоритма все оставшиеся элементы массива – суть простые числа от 3 до N.

Пример работы альтернативного алгоритма до N=99

Сформируем массив из нечетных чисел от 3 до 99.

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

цикл 1: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99;

цикл 2: 25, 35, 45, 55, 65, 75, 85, 95;

цикл 3: 49, 63, 77, 91;

цикл 4: 81, 99.

Исключим из массива нечетных чисел элементы с найденными значениями (при на шаге 3 работа алгоритма будет завершена, поскольку условие:  выполняться не будет).

По завершению работы алгоритма в массиве останутся только нечетные простые числа от 3 до 97.

Псевдокод

Альтернативный алгоритм поиска нечетных простых чисел может быть представлен следующим псевдокодом:

вход: натуральное число

A – булевый массив, индексируемый числами от 3 до  и заполненный значениями

пока

пока

выход: числа  массива A, для которых

Примечание:  – индекс ячейки нечетного числа в массиве А.

Оценка вычислительной сложности и быстродействия

Вычислительная сложность алгоритмов Эратосфена и Сундарама оценивается как  и  соответственно, что обуславливает их высокую эффективность в диапазоне до .

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

с учетом асимптотической формулы Эйлера для суммы первых N членов гармонического ряда [4], общее число итераций цикла можно представить как:

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

Однако, на практике не всегда алгоритм с лучшей асимптотической сложностью является более производительным. Кроме того, быстродействие алгоритма зависит от ряда других факторов: мощности процессора, объема оперативной памяти, используемого программного кода, наличия оптимизаций, а также от скорости выполнения арифметических операций на вычислительных машинах [5, P. 444-445].

С целью определения фактического быстродействия альтернативного алгоритма были проведены его тестовые испытания, которые показали высокую скорость исполнения алгоритма, сопоставимую со скоростью работы решета Эратосфена по нечетным числам. Для улучшения эффективности альтернативного алгоритма представляется возможной его оптимизация за счет применения сегментирования и битового сжатия.

Заключение

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

Таким образом, представленный альтернативный алгоритм является еще одним простым и эффективным способом поиска простых чисел наряду с известными алгоритмами Эратосфена и Сундарама.

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

1. Horsley, Rev. Samuel, F.R.S. Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers // Philosophical Transactions (1683-1775), Vol. 62. (1772). P. 327-347.
2. V. Ramaswami Aiyar. (1934) Sundaram's Sieve for prime numbers // The Mathematics Student. 1934. 2 (2): 73.
3. Серпинский В. Что мы знаем и чего не знаем о простых числах / пер. с польск. Мельников И.Г. – М.-Л.: Физматгиз, 1963. – 92 c.
4. Большая российская энциклопедия [электронный ресурс]: Гармонический ряд – Режим доступа: https://bigenc.ru/c/garmonicheskii-riad-d5681b (дата обращения 30.01.2025).
5. R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective, second edition. – Springer, 2005. – 597 p.