2 / 9
зации [4]. Суть метода заключается в следующем: перемножаются не-
сколько первых простых чисел, идущих подряд (математическая опе-
рация, известная как примориал), например,
3# = 2
×
3 = 6
,
5# = 2
×
×
3
×
5 = 30
,
7# = 2
×
3
×
5
×
7 = 210
и т.д. Затем строится таблица
с числом столбцов, равным полученному примориалу, ячейки которой
нумеруются по порядку (рисунок) [5]. При этом для обобщения доба-
влена кольцевая факторизация для
2# = 2
. В построенных таблицах
выделим столбцы, которые начинаются с единицы, с простых чисел,
не участвовавших в получении примориала, а также со всевозможных
произведений этих простых чисел, меньших примориала.
Согласно методу кольцевой факторизации, в неотмеченных столб-
цах находятся только составные числа, за исключением всех участ-
вовавших в получении примориала простых чисел (расположены в
первых строках таблиц).
Далее исключим из рассмотрения неотмеченные столбцы, при этом
учитывая все участвовавшие в получении примориала простые числа.
Очевидно, что в отмеченных столбцах находятся простые числа, а так-
же единица и оставшиеся после предварительного отбора составные
числа. Определим понятие “порядок кольцевой факторизации”.
Определение 1.
Порядок кольцевой факторизации
—
число со-
множителей примориала, используемого при построении соответ-
ствующей таблицы предварительного отбора составных чисел.
Метод кольцевой факторизации позволяет отсеять значительную
часть составных чисел: для
3#
отсеивается 66,66% всех составных
чисел; для
7#
— более 77%; для
251#
— около 90%.
На следующем этапе для исключения оставшихся составных чи-
сел применяют различные алгоритмы, например, решето Эратосфена,
решето Аткина и др., а также современные алгоритмы, основанные
на индексном представлении составных чисел в натуральном ряде [1,
4–6]. Сравнение быстродействия индексного алгоритма с решетом Ат-
кина, из результатов которого следует, что индексный алгоритм на
исследованном отрезке натурального ряда работает в 12 раз быстрее
проведено в работе [7].
Табличное отображение кольцевой факторизации для 2# (
а
), 3# (
б
) и 5# (
в
)
90 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1