[Project Euler]Problem 7

时间：2011-05-11 来源：class

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]