{"ID":2853295,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16285","arxiv_id":"2510.16285","title":"A Note on Algorithms for Computing $p_n$","abstract":"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.","short_abstract":"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 Hy...","url_abs":"https://arxiv.org/abs/2510.16285","url_pdf":"https://arxiv.org/pdf/2510.16285v1","authors":"[\"Ansh Aggarwal\"]","published":"2025-10-18T00:49:08Z","proceeding":"math.NT","tasks":"[\"math.NT\",\"cs.DS\"]","methods":"[]","has_code":false}