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).
Download file
Counter downloads: 328
- Title On the complexity of computing prime tables on the Turing machine
- Headline On the complexity of computing prime tables on the Turing machine
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(31)
- Date:
- DOI
Keywords
машина Тьюринга, сложность, просеивание, Turing machine, complexity, sievingAuthors
References
Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. М.: Вильямс, 2008. 832 c.
Sandor J., Mitrinovic D. S., and Crstici B. Handbook of Number Theory. I. Dordrecht: Springer, 2006. 622 p.
Rosser J. and Schoenfeld L. Approximate formulas for some functions of prime numbers // Ill. J. Math. 1962. V.6. P. 64-94.
Atkin A.O.L. and Bernstein D. J. Prime sieves using binary quadratic forms // Math. Comput. 2004. V. 73. No. 246. P. 1023-1030.
Mairson H. G. Some new upper bounds on the generation of prime numbers // Comm. ACM. 1977. V. 20. No. 9. P. 664-669.
Farach-Colton M. and Tsai M.-T. On the complexity of computing prime tables. arXiv:1504. 05240. 2015.
Furer M. How fast can we multiply large integers on an actual computer? arXiv:1402.1811. 2014.
Pritchard P. A sublinear additive sieve for finding prime numbers // Comm. ACM. 1981. V. 24. No. 1. P. 18-23.
Schonhage A., Grotefeld A. F. W., and Vetter E. Fast Algorithms: a Multitape Turing Machine Implementation. Mannheim, Leipzig, Wien, Zurich: Bl-Wissenschaftsverlag, 1994. 298 p.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 c.
Крэндалл Р., Померанс К. Простые числа: криптографические и вычислительные аспекты. М.: УРСС: Либроком, 2011. 664 с.
On the complexity of computing prime tables on the Turing machine | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 1(31).