RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive
Prikl. Diskr. Mat., 2016 Number 1(31), Pages 86–91 (Mi pdm536)
Computational Methods in Discrete Mathematics

On the complexity of computing prime tables on the Turing machine

I. S. Sergeev

Technology Federal State Unitary Enterprise "Research Institute Kvant", Moscow, Russia

Abstract: It is proved that the complexity of computing the table of primes up to $n$ on a multitape Turing machine is O$(n\log n)$.

Keywords: Turing machine, complexity, sieving.

UDC: 519.71

DOI: 10.17223/20710410/31/8



Bibliographic databases:

© Steklov Math. Inst. of RAS, 2025