素数生成器花费过多时间

通过上市前六个质数：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

但它采取了大量的时间。
我该如何加快速度？

来源

2013-03-14 svineet

你使用什么算法？ – Paul 2013-03-14 05:03:59

你的'checkPrime'是错误的。 'range（1，x）'的最后一个元素是'x-1'，所以你实际上找到的是只有3个除数的数字，即素数的平方。如果你改正了这种情况，通过将'facs'初始化为1或者通过检查'range（1，x + 1）'，运行时间将从几千年下降到一小时左右（给出或取10倍）它会给出正确的答案。当然，你还是会想用一个体面的素数测试，在平方根处停下来。 – 2013-03-17 11:53:01

的一种方式通过使用素数测试来完成：

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-14 05:18:30 Jared

你不需要使用Eratosthenes的筛子为此（虽然你会在将来的问题）。发现10001素数相对较快。

注意事项：

只测试奇数（除了＃2）
您只需要测试除数到价值的平方根。

扰流板下面 - 假设你已经解决了这个问题，但它只是需要很长的时间在C＃

例（对不起，不知道蟒蛇）：

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-14 05:12:43 Inisheer

我不明白为什么“你只需要测试除数，直到价值的平方根。”你能否详细解释一下？ – m3dl 2016-04-21 16:54:45

因为其他人都被张贴他们的解决方案，我想我会包括一些明显的改进，以简单的除法方法：

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-14 05:27:17 Voo

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

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

来源

2013-03-14 05:29:33 ymn

素数生成器花费过多时间

回答

相关问题