素數生成器花費過多時間

通過上市前六個質數：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

素數生成器花費過多時間

回答

相關問題