Instruments and Systems: Monitoring, Control, and Diagnostics Annotation << Back Algorithm for Construction of Natural Number Factorization Data Structure and Estimation of its Asymptotic Complexity D.V. POLYAKOV, E.U. VELEGURINA In the article an algorithm for constructing a data structure is given which based on a range of natural numbers limited from above. This structure allows factorization of numbers from a given range in the worst case in logarithmic time and checking for primality in constant time. A side effect of constructing the proposed structure is to fi nd all prime numbers in a given range and represent them as a doubly linked list. The paper provides an estimate of the asymptotic complexity of all proposed algorithms, including showing that the asymptotic complexity of constructing the proposed structure does not exceed linear. An approach to using the constructed algorithms and data structure to implement long arithmetic in factorized form is proposed. A class of applied problems is considered, for the solution of which it is advisable to use long arithmetic in factorized form with the proposed factorization algorithm. Keywords: factorization, primality testing, prime number, construction of series of prime numbers, algorithm, asymptotic characteristic, index array, doubly linked list, long arithmetic, combinics, Bernstein polynomial. DOI: 10.25791/pribor.10.2023.1448 Pp. 32-50.