4

我正在解决问题：

通过列出前六个素数：2、3、5、7、11 和 13，我们可以看到第 6 个素数是 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

但这需要很多时间。
我怎样才能加快速度？

4

4 回答 4

5

一种使用素数测试的方法：

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 秒内运行。对这个问题没关系，但正如其他人所说，筛子更有效。

于 2013-03-14T05:18:30.830 回答
4

您可以使用素数定理来很好地估计您必须走多远。（估计程序中数组 p 的大小）。pi(n), 小于n, 的素数个数是渐近的n%^.n（n除以ln n）。对于第 10001 个素数，等式是，并且为您10001=n%^.n求解得到介于 1.1e5 和 1.2e5 之间。nn

因此，您可以缩小检查值的范围并仅检查范围的数字。这种技术减少了程序的运行时间。

于 2013-03-14T05:29:33.593 回答
2

您不需要为此使用埃拉托色尼筛（尽管您将在未来的问题中使用）。找到 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();
    }
}
于 2013-03-14T05:12:43.400 回答
2

由于其他人都在发布他们的解决方案，我想我会对简单的除法方法进行一些明显的改进：

def is_prime(nr):
    if nr < 2: return false
    if nr < 4: return true
    if nr % 2 == 0: return false
    if nr < 9: return true
    if nr % 3 == 0: return false
    for i in range(5, int(nr**0.5) + 1, 6):
        if number % i == 0: return false
        if number % (i + 2) == 0: return false
    return true

通过摆脱一个不必要的模运算，这改进了简单的解决方案。

于 2013-03-14T05:27:17.230 回答