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