007. 第10001个质数(10001st prime)

列出前六个质数,我们可以发现第六个质数为13,那么第10001个质数是多少?

分析:一般而言,对于第\(n\)个素数\(p_n\),满足以下不等式(参见素数计数函数):

$$ ln(nln(n))-1<\frac{p_n}{n}<ln(nln(n)) $$

在这里我们只关注上界,则可以得到\(p_n<nln(nln(n))=nln(n)+nln(ln(n))\),我们先筛选出从2到上界的所有质数,再取其中的第10001个质数,即得到结果。

from sympy import primerange
from math import log,ceil

def main(n=10001):
    upper_bound = ceil((log(n)+log(log(n))) * n)
    primes = list(primerange(1,upper_bound))
    return primes[n-1]