arXiv Open Access 2016

On the complexity of computing prime tables on a Turing machine

Igor S. Sergeev

Lihat Sumber

Abstrak

We prove that the complexity of computing the table of primes between $1$ and $n$ on a multitape Turing machine is $O(n \log n)$.

cs.DS

Igor S. Sergeev

APA MLA BibTeX

Sergeev, I.S. (2016). On the complexity of computing prime tables on a Turing machine. https://arxiv.org/abs/1604.01154

Lihat di Sumber

Informasi Jurnal