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