⌘+K

Pulse Explore Communities Researchers Journals

Browser extensionInstagram

Home Communities Explore

March 1, 2016PRIKLADNAYa DISKRETNAYa MATEMATIKA

On the Complexity of Computing Prime Tables on the Turing Machine

View at Publisher

Ask AI

Bookmark

Share

Ask about this paper

Answers are grounded in this paper and cite their sources.

Ask your own question…

Abstract

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).

Discussion

No takes yet. Share an insight, caveat, or question.

Cite This Study

I. S. Sergeev (2016) studied this question.

synapsesocial.com/papers/6a1bf22d666b677c61a90d9d https://doi.org/10.17223/20710410/31/8

View at Publisher

Ask AI

Bookmark

Share

Keep reading

Synapse has enriched 7 related papers. Consider them for comparative context:

1On the Existence of Directed Strongly Regular Graphs With Parameters (22, 9, 6, 3, 4)PRIKLADNAYa DISKRETNAYa MATEMATIKA · 2024
2Zero-knowledge succinct non-interactive arguments of knowledge based on sets of polynomialsPRIKLADNAYa DISKRETNAYa MATEMATIKA · 2023
3Binary solutions to large systems of linear equationsPRIKLADNAYa DISKRETNAYa MATEMATIKA · 2021
4Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automataPRIKLADNAYa DISKRETNAYa MATEMATIKA · 2018
5Fast Method for Generating Random Geometric Graphs for Wireless Networks ModellingPRIKLADNAYa DISKRETNAYa MATEMATIKA · 2016
6Circular Inversions of Permutations and Their Use in Sorting ProblemsPRIKLADNAYa DISKRETNAYa MATEMATIKA · 2016
7Inverse Dynamical Systems With Variable Dimension of Phase Space in Problems of Cryptographic Information TransformationPRIKLADNAYa DISKRETNAYa MATEMATIKA · 2008

PMore from PRIKLADNAYa DISKRETNAYa MATEMATIKA