4 / 9
Индексный алгоритм произвольного порядка для отсева
составных чисел из таблицы кольцевой факторизации.
Отсев
оставшихся после кольцевой факторизации составных чисел из мно-
жеств
{
q
−
p
n
+
s
p
n
#
∙
k
}
, . . . ,
{
q
−
p
n
+
r
p
n
#
∙
k
}
, . . . ,
{
q
−
p
n
+1
p
n
#
∙
k
}
,
{
q
−
1
p
n
#
∙
k
}
,
{
q
+1
p
n
#
∙
k
}
,
{
q
+
p
n
+1
p
n
#
∙
k
}
,
. . . ,
{
q
+
p
n
+
r
p
n
#
∙
k
}
, . . . ,
{
q
+
p
n
+
s
p
n
#
∙
k
}
, где
k
= 0
,
1
,
2
, . . . k
max
. Кратные числу
q
∈ {
Q
}
=
{
p
n
#
∙
i
−
p
n
+
s
} ∪
. . .
∪ {
p
n
#
∙
i
−
p
n
+
r
} ∪
. . .
∪ {
p
n
#
∙
i
−
p
n
+1
} ∪ {
p
n
#
∙
i
−
1
} ∪ {
p
n
#
∙
i
+ 1
} ∪ {
p
n
#
∙
i
+
+
p
n
+1
}∪
. . .
∪{
p
n
#
∙
i
+
p
n
+
r
}∪
. . .
∪{
p
n
#
∙
i
+
p
n
+
s
}
, где
i
= 0
,
1
,
2
, . . . , i
max
(для максимально возможного
i
=
i
max
должно быть выполнено усло-
вие
q
−
p
n
+
s
p
n
#
∙
i
max
2
≤
N
max
,
r
= 1
,
2
,
3
, . . . , s
, составные числа можно
исключить, вычислив их индексы. Для этого каждому
q
∈ {
Q
}
соот-
ветствует свой паттерн
t
j
q
, q
∈ {
Q
}
,
(2)
т.е. схема размещения чисел, кратных
q
, в строках с индексами
l
q
2
m
, . . .
3
q
2
табл. 1. Этот паттерн повторяется в строках с индекса-
ми
m
∙
q
+
l
q
2
m
, . . . , m
∙
q
+
3
q
2
, где
m
= 0
,
1
,
2
, . . .
, что показано в
работе [2].
Рассмотрим в качестве примера отсеивание чисел, кратных
q
=
=
q
+7
30
∙
0
= 7
, при выполнении индексного алгоритма третьего порядка.
Напомним, что третий порядок индексного алгоритма означает, что
нужно взять три первых простых числа и перемножить их:
2
×
3
×
×
5 = 30
, после чего составить таблицу симметричной кольцевой
факторизации, содержащую все простые числа и состоящую из членов
прогрессий
{
30
k
−
13
}
=
{
30(
k
−
1) + 17
}
,
{
30
k
−
11
}
=
{
30(
k
−
1) +
+ 19
}
,
{
30
k
−
7
}
=
{
30(
k
−
1) + 23
}
,
{
30
k
−
1
}
=
{
30(
k
−
1) + 29
}
,
{
30
k
+ 1
}
,
{
30
k
+ 7
}
,
{
30
k
+ 11
}
,
{
30
k
+ 13
}
. Для того чтобы отсеять
все числа, кратные 7, нужен паттерн (2) для числа 7:
t
j
q
=
{
3
,
2
,
0
,
−
3
,
3
,
0
,
−
2
,
−
3
}
,
для
j
=
−
4
,
−
3
,
−
2
,
−
1
,
1
,
2
,
3
,
4
, q
= 7
.
(3)
Далее следует во множестве диапазонов индексов
{
[11; 17]
,
[18; 24]
, . . .
}
исключить соответственно паттерну (3) числа, крат-
ные 7. Описанный процесс показан в табл. 2, полученной из табл. 1
при
n
= 3
.
Обратим внимание на то, что паттерн
t
j
q
обладает в данном слу-
чае свойством центральной симметрии относительно
q
. Это свойство
является общим для любого паттерна, как следствие построения таб-
лицы симметричной кольцевой факторизации.
Более подробно примеры паттернов рассмотрены в работе [2].
Таким образом, если в заданном отрезке
[
N
min
;
N
max
] с помощью со-
ответствующих паттернов (2) отсеять составные числа, кратные всем
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6 85