5 / 9
Таблица 2
Пример адресации составных чисел при
q
=
q
+7
30
∙
0
= 7
подходящим
p
, то в нем останутся только простые числа. Более того,
достаточно рассмотреть только простые
p
∈ {
Q
}
, поскольку состав-
ные будут высеивать те числа, которые уже отсеяны простыми до них.
Отметим, что число паттернов равно числу элементов множества
{
Q
}
,
которое зависит от значения
N
max
. Следовательно, на отрезках равного
размера с различным
N
max
число паттернов будет больше у отрезка с
большим
N
max
. Перейдем к описанию некоторых программных моди-
фикаций индексного алгоритма.
Модификация индексного алгоритма для параллельных вы-
числений.
Поскольку алгоритм построен таким образом, что может
независимо обрабатывать заданный ему отрезок натурального ряда,
то задачу поиска всех простых чисел на определенном большом от-
резке можно разбить на подзадачи поиска на частях этого отрезка.
Такой подход позволяет при программной реализации алгоритма ис-
пользовать сразу две модификации: блочный подход и параллельные
вычисления.
При использовании параллельных вычислений потоки могут яв-
но взаимодействовать между собой через разделяемую память и/или
через передачу сообщений. В нашем случае можно использовать оба
типа взаимодействий, т.е. вести обмен данными между потоками на
узле посредством общей памяти, а между узлами — с помощью пере-
дачи сообщений. Такой способ программирования более сложен, но
86 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6