Приборы и системы. Управление, контроль, диагностика Аннотация к статье << Назад Структура данных и основанные на ней алгоритмы факторизации натуральных чисел в заданном диапазоне Д.В. ПОЛЯКОВ, Е.Ю. ВЕЛЕГУРИНА В статье предложена структура данных, на основе подпоследовательности натурального ряда, содержащей все простые числа. Эта структура позволяет осуществлять факторизацию чисел из заданного диапазона в худшем случае за логарифмическое время, в лучшем за длину факторизации, а проверку на простоту за константное время. В работе приведена оценка асимптотической сложности всех предложенных алгоритмов. Также в работе приведена математическая модель, на основе которой строится предложенная структура данных. В рамках приведенной математической модели вводится в рассмотрение подпоследовательность натурального ряда, содержащая все простые числа. Приводятся примеры членов рассмотренной подпоследовательности и оценивается их рост в сравнении с ростом ряда натуральных и простых чисел. Ключевые слова: высшая арифметика, теория чисел, факторизация, проверка на простоту, простое число, структура данных, алгоритм, асимптотическая сложность, индексный массив, двусвязный список. DOI: 10.25791/pribor.9.2023.1442 Стр. 47-62.