Реализация индексных алгоритмов поиска простых чисел с помощью параллельных вычислений

3 / 9

интервале (pn; pn#/2); r = 1, 2, 3, . . . , s; j — номер столбца кольцевой
факторизации.
В центральном столбце табл. 1 приведена последовательность ин-
дексов 0, 1, 2, . . . , k max, в остальных столбцах — отображения этой по-
следовательности во множества вида {p n# ∙ k − pn+s }, . . . , {p n# ×
× k − pn+r }, . . . , {pn# ∙ k − pn+1 }, {pn# ∙ k − 1 }, {pn# ∙ k + 1}, {pn# ×
× k + pn+1 }, . . . , {pn# ∙ k +p n+r} , . . . , {pn# ∙ k + pn+s}, содержащие как
простые, так и составные числа, а также единицу.
Таблица 1
Результаты симметричной кольцевой факторизации для p n #
в табличном виде
Правило знаков произвольного порядка при построении таб-
лицы кольцевой факторизации. Для определения индексов простых
чисел в каждом столбце таблицы кольцевой факторизации второго
порядка в работе [4] предложены соотношения для составных чисел
из столбцов таблицы кольцевой факторизации, называемые “правилом
знаков”. В работе [2] эти соотношения обобщены на произвольный
порядок:
c
+pn+r1 ∙pn+r2
q −p n +r1
pn#∙i
= q−pn+r1
pn#∙i ∙ q−pn+r2
pn #∙m = (pn # ∙ i − p n+r1 ) ∙ (pn# ∙ m − pn+r 2 );
c+pn+r1 ∙pn+r2
q
+pn 1
pn#∙i
= q+pn+r1
pn#∙i ∙ q+pn+r2
pn #∙m = ( pn # ∙ i + p n+r 1 ) ∙ (pn # ∙ m + p n+r2 );
c−pn+r1 ∙pn+r2
q −p n +r1
pn#∙i
= q−pn+r1
pn#∙i ∙ q+pn+r2
pn #∙m = ( pn # ∙ i − p n+r 1 ) ∙ (pn# ∙ m + p n+r 2);
c−pn+r1 ∙pn+r2
q
+p n +r1
pn#∙i
= q
+pn+r1
pn#∙i ∙ q−pn+r2
pn #∙m = ( pn # ∙ i + p n+r 1 ) ∙ (pn # ∙ m − p n+r 2) .
(1)
Чтобы получить все формулы составных чисел, нужно записать вы-
ражения (1) со всеми сочетаниями значений r1 и r2 из ряда 1, 2, 3, . . . , s ,
кроме этого, согласно методу кольцевой факторизации, нужно в ряде
случаев вместо pn+r 1 и/или p n+r2 ставить единицу. В работе [2] опре-
делен принцип, основанный на соотношениях (1), согласно которому
составные числа и расположены в табл. 1.
84 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6