##By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
##that the 6th prime is 13.
##What is the 10001st prime number?
def f(n):
    result=[2]
    i=3
    while len(result)<n:
        for j in result:
            if i%j==0:
                break
            elif j*j>i:
                result.append(i)

                break
        i=i+2
    return result[-1]
def sieve(n):
    '''使用[0,1,2,...,((n-1)//2)-1]来表示[3,5,7,...,((n-1)//2)*2+1]'''
    if n<2:
        raise StopIteration
    yield 2
    if n>2:
        k=[True for i in range((n-1)//2)]
        for i in range((n-1)//2):
            val=2*i+3
            if val*val>n:
                for j in range(i,(n-1)//2):
                    if k[j]:
                        yield 2*j+3
                break
            if k[i]:
                yield val
                for j in range(i+val,(n-1)//2,val):
                    k[j]=False
from math import log
def f2(n):
    ps=list(sieve(int(n*log(n)*1.2)))
    return ps[n-1]
def f3(n):
    if n==1:
        return 2
    else:
        Step=10000
        ps=list(sieve(2*Step+2))[1:]
        ##求第一个分段3- 2*Step+3的素数，然后去掉2。
        if n-2<len(ps):
            return ps[n-2]
        else:
            begin=3
            k=[True for i in range(Step)]
            while n-2>=len(ps):
                begin+=2*Step
                ##使用[0,1,2,...,Step-1]来表示[begin,begin+2,...begin+2*Step-2]
                end=2*Step+begin-2
                for i in range(Step):
                    k[i]=True
                for i in ps:
                    if i*i>end:
                        for j in range(Step):
                            if k[j]:
                                ps.append(2*j+begin)
                        break
                    NumModeI=((begin-1)//i)*i+i
                    ##求出比 大于或等于begin的最小的能被i整除的整数
                    if NumModeI%2==0:
                        NumModeI+=i
                    for j in range((NumModeI-begin)//2,Step,i):
                        k[j]=False
            return ps[n-2]
def f4(n):
    if n==1:
        return 2
    else:
        Step=1000
        ps=[list(sieve(2*Step+2))[1:]]
        if n-2<len(ps[0]):
            return ps[0][n-2]
        else:
            begin=3
            k=[True for i in range(Step)]
            R=len(ps[0])
            while n-2>=R:
                begin+=2*Step
                Val_Max=2*Step+begin-2
                for i in range(Step):
                    k[i]=True
                for i in (i for p in ps for i in p):
                    if i*i>Val_Max:
                        ps.append([2*j+begin for j in range(Step) if k[j]])
                        break
                    Temp=((begin-1)//i)*i+i
                    if Temp%2==0:
                        Temp+=i
                    for j in range((Temp-begin)//2,Step,i):
                        k[j]=False
                R+=len(ps[-1])
            return ps[-1][n-R-2]

val=300001
from timeit import Timer
##def test():
##    re=f(val)
####    print(re)
##t=Timer("test()","from __main__ import test")
##print("f:",t.timeit(1))

def test2():
    re=f2(val)
##    print(re)
t2=Timer("test2()","from __main__ import test2")
print("f2:",t2.timeit(1))

def test3():
    re=f3(val)
##    print(re)
t3=Timer("test3()","from __main__ import test3")
print("f3:",t3.timeit(1))

##def test4():
##    re=f4(val)
####    print(re)
##t4=Timer("test4()","from __main__ import test4")
##print("f4:",t4.timeit(1))
