尋找10001素 - 如何優化？

通過上市前六個質數：2，3，5，7，11，13，我們可以看到，第六屆主要是13.什麼是第一萬○一素數？

下面是我用Python編寫的代碼：

def primes(n): 
    primes = [] 
    attempt = 3 
    while len(primes) < (n-1): 
     for i in range(len(primes)): 
      if attempt % primes[i] == 0: 
       attempt += 2 
       break 
     else: 
      primes.append(attempt) 
      print (primes) 
    return (primes)

在測試一個數字，如果發現該號碼整除列表中的素數之一，for循環中斷，並以更大的數字重新開始。如果它不能被整除，它會被添加到素數列表中。這一直持續下去，直到列表的大小足夠大（在這種情況下是10000，而我省略了2，因此列表的最後一個成員是10001st素數）

問題是，這是非常慢的。我已經看到其他可以明顯解決這個問題的解決方案是秒，如果不是更少。有什麼方法可以讓我更快樂？

來源

2015-09-01 Nicholas Hassan

尋找術語「總理篩」可能會給你有用的結果。 – Kevin

[Eratosthenes的篩子]（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes） –

此外，只需使用'numpy'對數值進行簡單的更改就可以加快速度，不要使用for-loop，手段。 – zeroth

這些都是優化問題，所以您不希望每次更新列表時都要打印。另一件事是根本不使用列表，因爲不是很有效率的記憶。你應該使用生成器。它非常快速，你不會使用列表來消耗內存。以下是用於此目的的代碼，請觀察yield關鍵字如何用於將count_primes函數轉換爲生成器。

def is_prime(num): 
    """ 
    Checks if a number is prime 
    """ 
    prime_counter = 1 
    for x in range(1, num): 
     if num % x == 0: 
      prime_counter += 1 
     if prime_counter > 2: 
      return False 
    return True 


def count_primes(): 
    """ 
    Counts primes until PRIMES_TO_COUNT 
    is reached 
    """ 
    PRIMES_TO_COUNT = 1000  # Modify this value 
    prime_counter_num = 0 
    start_point_num = 1 
    while True: 
     if is_prime(start_point_num): 
      if prime_counter_num == PRIMES_TO_COUNT: 
       yield start_point_num 
       print "This is the %dth prime number: %s" \ 
         % (prime_counter_num, start_point_num) 
       break 
      prime_counter_num += 1 
     start_point_num += 1 


if __name__ == '__main__': 
    for prime_number in count_primes(): 
     print prime_number

希望這可以幫助你！ Python generators!

來源

2015-09-01 18:21:53 user2709479

-1

而不是檢查每個奇數你可以檢查形式6n±1的所有數字，因爲所有素數都是這種形式。

來源

2017-01-01 15:13:39 4manshenoy

尋找10001素 - 如何優化？

回答

相關問題