A Note on Algorithms for Computing p_n

2025/10/18 by Aggarwal, Ansh
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2510.16285

openalex publication_date 2025/10/18 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28

Abstract

We analyze algorithms for computing the nth 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(√(n) (log n)⁴) 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(√(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.

Citations

• New estimates for the nth prime number
• Estimates of Some Functions Over Primes without R.H.

Related

• An algorithm for the prime-counting function of primes larger than three
• Computing π(N): An elementary approach in O(√(N)) time
• Algorithm, probability, and prime numbers
• The combinatorial algorithm for computing pi(x)
• Problems on combinatorial properties of primes