Geodesic
On the complexity of computing prime tables on the Turing machine
Prikladnaâ diskretnaâ matematika, no. 1 (2016), pp. 86-91.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDM_2016_1_a7,
     author = {I. S. Sergeev},
     title = {On the complexity of computing prime tables on the {Turing} machine},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {86--91},
     publisher = {mathdoc},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_1_a7/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On the complexity of computing prime tables on the Turing machine
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 86
EP  - 91
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_1_a7/
LA  - ru
ID  - PDM_2016_1_a7
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On the complexity of computing prime tables on the Turing machine
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 86-91
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_1_a7/
%G ru
%F PDM_2016_1_a7
I. S. Sergeev. On the complexity of computing prime tables on the Turing machine. Prikladnaâ diskretnaâ matematika, no. 1 (2016), pp. 86-91. http://geodesic.mathdoc.fr/item/PDM_2016_1_a7/

[1] Crandall R., Pomerance C., Prime Numbers. A Computational Perspective, Springer, 2005, 597 pp. | MR | Zbl

[2] Schönhage A., Grotefeld A. F. W., Vetter E., Fast Algorithms: a Multitape Turing Machine Implementation, BI-Wissenschaftsverlag, Mannheim–Leipzig–Wien–Zürich, 1994, 298 pp. | MR | Zbl

[3] Aho A., Hopcroft J., Ullman J., The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1974 | MR | Zbl

[4] Fürer M., How fast can we multiply large integers on an actual computer?, 2014., arXiv: 1402.1811 | MR

[5] Pritchard P., “A sublinear additive sieve for finding prime numbers”, Comm. ACM, 24:1 (1981), 18–23 | DOI | MR | Zbl

[6] Farach-Colton M., Tsai M.-T., On the complexity of computing prime tables, 2015, arXiv: 1504.05240

[7] Atkin A. O. L., Bernstein D. J., “Prime sieves using binary quadratic forms”, Math. Comput., 73:246 (2004), 1023–1030 | DOI | MR | Zbl

[8] Mairson H. G., “Some new upper bounds on the generation of prime numbers”, Comm. ACM, 20:9 (1977), 664–669 | DOI | MR | Zbl

[9] Rosser J., Schoenfeld L., “Approximate formulas for some functions of prime numbers”, Ill. J. Math., 6 (1962), 64–94 | MR | Zbl

[10] Sándor J., Mitrinović D. S., Crstici B., Handbook of Number Theory, v. I, Springer, Dordrecht, 2006, 622 pp. | MR | Zbl

[11] Knuth D. E., The Art of Computer Programming, v. 3, Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1998 | MR