A Note on Algorithms for Computing $p_n$
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908600645976064 |
|---|---|
| author | Aggarwal, Ansh |
| author_facet | Aggarwal, Ansh |
| contents | We analyze algorithms for computing the $n$th prime $p_n$ and establish asymptotic bounds for several approaches. Using existing results on the complexity of evaluating the prime-counting function $π(x)$, we show that the binary search approach computes $p_n$ in $O(\sqrt{n} \, (\log n)^4)$ time. Assuming the Riemann Hypothesis and Cramér's conjecture, we construct a tighter interval around li$^{-1}(n)$, leading to an improved sieve-based algorithm running in $O(\sqrt{n} \, (\log ^{7/2} n) \, \log \log n)$ time. This improvement, though conditional, suggests that further refinements to prime gap estimates may yield provably faster methods for computing primes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16285 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on Algorithms for Computing $p_n$ Aggarwal, Ansh Number Theory Data Structures and Algorithms We analyze algorithms for computing the $n$th prime $p_n$ and establish asymptotic bounds for several approaches. Using existing results on the complexity of evaluating the prime-counting function $π(x)$, we show that the binary search approach computes $p_n$ in $O(\sqrt{n} \, (\log n)^4)$ time. Assuming the Riemann Hypothesis and Cramér's conjecture, we construct a tighter interval around li$^{-1}(n)$, leading to an improved sieve-based algorithm running in $O(\sqrt{n} \, (\log ^{7/2} n) \, \log \log n)$ time. This improvement, though conditional, suggests that further refinements to prime gap estimates may yield provably faster methods for computing primes. |
| title | A Note on Algorithms for Computing $p_n$ |
| topic | Number Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.16285 |