A Note on Algorithms for Computing p_n
Ansh Aggarwal
我们分析用于计算第 n 个素数 p_n 的算法,并为几种方法建立渐近边界。 使用评估素数函数π(x)的复杂性的现有结果,我们显示二进制搜索方法在O(√(n)(log n)^4)时间计算p_n。 假设黎曼假说和Cramér的猜想,我们在li^-1(n)周围构建了一个更严格的间隔,导致在O(√(n)(log ^7/2 n) loglog n)时间上运行的基于筛子的改进算法。 这种改进虽然有条件,但表明对素数差距估计的进一步改进可能会产生出更快的计算素数方法。
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)^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(√(n) (log ^7/2 n) loglog n) time. This improvement, thoug...
