首页 | 新闻 | 交流 | 问吧 | 文档 | 手册 | 下载 | 博客

[Project Euler]Problem 7

作者:  时间: 2011-05-11

Problem7:
  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?

问题7:
  通过列出前六个素数: 2,3,5,7,11,13,我们可以知道第6个素数为13。
  求第10001个素数? 

方法一:
  一个一个数判断是否为素数,知道第n个素数: 

方法一
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]

方法二:
  方法一的缺点 很明显,速度比较慢。
  求素数的比较快的方法为 筛法 ,不过筛法是用来求 小于某个数的所有素数的。我们要先知道第n个素数有多大,然后才能使用筛法。
  根据素数定理,我们可以使用  n*ln(n)*1.2为界来求,对于n>50,都有第n个素数小于 n*ln(n)*1.2。

方法二
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]

方法三:
  方法二需要判断上界,而且上界不一定有效,这是方法二的缺点。
  我们对筛法进行改进。对数进行分段,使用筛法求出每一段的素数,直到我们得到第n个素数。

方法三
def f3(n):
if n==1:
return 2
else:
Step
=1000
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]