生成素数的时间太长

Question

我正在解决一个问题：

通过列出前六个质数：2、3、5、7、11和13，我们可以看到第六个质数是13。
那么，第10,001个质数是什么呢？

def checkPrime(x):
    facs = 0
    for i in range(1,x):
        if x%i==0:
            facs = facs + 1
    if facs == 2:
        return True
    else :
        return False

i = 1
noPrime = 0
done = False
while(done==False):
    i = i + 1
    print "i = {0} and noPrime={1}".format(i,noPrime)
    if checkPrime(i)==True:
        noPrime = noPrime + 1
        if noPrime==10001 :
            print i
            done=True

但是这花了很多时间。
我该如何加快速度呢？

Answer 1

你不需要使用埃拉托斯特尼筛法来解决这个问题（不过在以后的题目中你会用到）。找到第10001个质数其实挺快的。

需要注意的几点：

• 只测试奇数（除了2以外）
• 你只需要测试到这个数的平方根为止。

下面是剧透 - 假设你已经解决了这个问题，但花了很长时间

以下是C#的示例（抱歉，我不太会Python）：

class Program
{
    static bool IsPrime(int value)
    {
        if (value == 2) return true;
        if (value % 2 == 0) return false;

        // Test for divisors up to the square root of "value", increment by 2.
        for (int i = 3; i <= Math.Sqrt(value); i += 2)
        {
            if (value % i == 0)
                return false;
        }
        return true;
    }

    static void Main(string[] args)
    {
        int primeCount = 1; // #2

        // Test only odd numbers.
        for (int i = 3; ; i += 2)
        {
            if (IsPrime(i))
            {
                primeCount++;
                if (primeCount == 10001)
                {
                    Console.WriteLine(i.ToString());
                    break;
                }
            }
        }
        Console.ReadLine();
    }
}

Answer 2

你可以使用素数定理来大致估算一下你需要查找的范围有多大。这是为了估算程序中数组p的大小。pi(n)表示小于n的素数数量，按照数学上的说法，它大约等于n除以ln n。如果我们想找第10001个素数，可以用公式10001=n%^.n来计算，解这个方程后，你会发现n的值大概在1.1e5到1.2e5之间。

所以，你可以缩小需要检查的数值范围，只检查这个范围内的数字。这样做可以减少程序的运行时间。

Answer 3

这里有一种方法可以通过质数测试来实现：

def isPrime(n):
    if n == 2: return True
    if n % 2 == 0 or n < 2: return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0: return False
    return True
if __name__ == "__main__":
    n = count = 1
    while count < 10001:
        n += 2
        if isPrime(n): count += 1
    print n

这个方法运行大约需要0.2秒。虽然对于这个问题来说时间并不重要，但正如其他人所说，筛法会更高效。