problem 7:


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?


版本一：


最原始的解法，花费的时间大概要20分钟左右。


    import time
    i=3
    num=1
    start=time.time()
    while 1:
        for j in range(2,i):
            if i%j==0:
                break
            elif j==i-1:
                num=num+1
                break
            else:
                continue
        if num==10001:
            print i
            break
        i=i+1
    end=time.time()
    print end-start


版本二：


优化后的解法，花费时间大概是55秒左右。


    import time
    i=3
    num=1
    S=[2]
    length=len(S)
    start=time.time()
    while 1:
        for j in S[0:length/2+1]:
            if i%j==0:
                break
            elif j==S[length/2]:
                S.append(i)
                length=length+1
                break
            else:
                continue
        
        if length==10001:
            print S[10000]
            break
        i=i+2
    end=time.time()
    print end-start


版本三：


进一步优化的解法，减少每次需要相除的个数，时间可以优化到不到3秒。


    import time, math
    i=3
    num=1
    S=[2]
    length=len(S)
    start=time.time()
    while 1:
        l=int(math.ceil(math.sqrt(length)))
        for j in S[0:l]:
            if i%j==0:
                break
            elif j==S[l-1]:
                S.append(i)
                length=length+1
                break
            else:
                continue
        
        if length==10001:
            print S[10000]
            break
        i=i+2
    end=time.time()
    print end-start


 


    import time, math
    def findprimefactor(num):
        primefactor=[2,3,5,7]
        i=9
        while len(primefactor)<num:
            flag=True
            q=int(math.sqrt(i))
            k=0
            while(primefactor[k]<=q):
                p=primefactor[k]
                if not(i%p):
                    flag=True
                    break
                else:
                    flag=False
                k+=1
            if not flag:
                primefactor.append(i)
            i+=2
        return primefactor
       
       
       
    if __name__=='__main__':
        start=time.time()
        result=findprimefactor(10001)
        print result[-1],"sec:",time.time()-start


版本四：利用埃拉托色尼选筛法来进行计算，花费的时间大概是0.8秒左右。


import math , time
limit=200000
L=[True]*limit


start=time.time()
def seive(x):
    for i in xrange(x*2,limit,x):
        L[i]=False
       
map(seive,[2])
map(seive,xrange(3,int(math.ceil(math.sqrt(limit))),2))


primer=[]
for i in xrange(2,limit):
    if L[i]:
        primer.append(i)
print primer[10000]
print time.time()-start