2 / 9
В настоящей работе описана суть индексного алгоритма, а также
выполнена оценка его быстродействия при параллельном просеива-
нии простых чисел в диапазоне до
10
12
на разных количествах ядер
вычислительной системы.
Модификации алгоритма, приведенные в настоящей работе, за-
ключаются в использовании битовых массивов, различных алгоритмов
для простых чисел разных размеров, предпросева для малых простых
чисел, блочного подхода, параллельных вычислений.
При описании метода использованы терминология и обозначения,
приведенные в работах [1–3].
Порядок индексного алгоритма, а также порядок таблицы кольце-
вой факторизации — это количество первых простых чисел, использо-
ванных при получении примориала для формирования соответствую-
щей кольцевой факторизации.
Переменная
k
— индекс числа на строке кольцевой факторизации
с соответствующим номером — введена для формирования таблицы
кольцевой факторизации.
Паттерн — повторяющаяся схема размещения составных чисел в
таблице кольцевой факторизации, кратных одному и тому же числу.
Как и во многих других, в индексном алгоритме поиска простых
чисел используется известный метод кольцевой факторизации. Он по-
зволяет не рассматривать значительную часть заведомо составных чи-
сел, а из остальных чисел сформировать таблицу, в каждой колонке
которой находятся как простые, так и составные числа.
Например, при использовании кольцевой факторизации второго по-
рядка отсеивается 66,66. . . % всех составных чисел, четвертого поряд-
ка — более 77%. Применение кольцевой факторизации подробно опи-
сано в работах [1–5]. В работе [2] для поиска простых чисел применен
подход, использующий свойство симметрии кольцевой факторизации
(табл. 1) и существенно экономящий вычислительные ресурсы при ре-
ализации индексных алгоритмов. В работе [3] выполнено сравнение
быстродействия индексного алгоритма с решетом Аткина, как одним
из самых эффективных методов поиска простых чисел. В результате
обнаружено, что индексный алгоритм на исследованном отрезке на-
турального ряда работает в 12 раз быстрее. Отметим, что индексный
алгоритм разработан авторами в РФ и в настоящее время публикаций
о подобного рода подходах в зарубежной печати нет.
В табл. 1 использованы принятые ранее обозначения [1–4]:
p
1
= 2
,
p
2
= 3
, . . . , p
n
— записанные по возрастанию простые числа;
p
n
#
—
примориал (произведение всех простых чисел, меньших либо рав-
ных
p
n
);
p
n
+1
, . . . , p
n
+
r
, . . . , p
n
+
s
— не участвовавшие в получении
p
n
#
простые числа и их произведения, меньшие
p
n
#
/
2
и записанные по
возрастанию;
s
— количество простых чисел и их произведений на
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6 83