從Python中隨機數列表過濾素數的最有效方法

我有一個填充隨機數的列表，我想從此列表中返回素數。所以，我創建了這些功能：從Python中隨機數列表過濾素數的最有效方法

def is_prime(number): 
    for i in range(2, int(sqrt(number)) + 1): 
     if number % i == 0: 
      return False 

    return number > 1

而且

def filter_primes(general_list): 
    return set(filter(is_prime, general_list))

但我想提高性能，所以我怎麼能做到這一點？

來源

2017-07-02 flpn

這裏有*噸的解決方案，特別是在SO上，顯示了主要檢查的實現。你有沒有檢查過他們？ – idjaw

不知道這是否有助於提高性能，因爲我沒有時間去測試任何東西，但是如果number> 1，則返回True，否則False可以歸結爲：return number> 1。 –

是的，有大量的素數檢查解決方案，但它們都不適用於隨機數列表的場景。 – flpn

Sieve of Eratosthenes，我的設備上以素數約0.17下秒千萬上PyPy 3.5：

from array import array 

def primes(upper): 
    numbers = array('B', [1]) * (upper + 1) 

    for i in range(2, int(upper ** 0.5) + 1): 
     if numbers[i]: 
      low_multiple = i * i 
      numbers[low_multiple:upper + 1:i] = array('B', [0]) * ((upper - low_multiple) // i + 1) 

    return {i for i, x in enumerate(numbers) if i >= 2 and x}

和濾波器功能：

filter_primes = primes(10_000_000).intersection

來源

2017-07-02 15:25:01 Ryan

一旦'我'達到'sqrt（上）''你已經確定了所有的素數。 – rici

這個篩子是否與隨機數列表一起工作？ – flpn

@flpn：不，但是如果所有的隨機數都是0-10,000,000，那麼您可以獲得該範圍內的所有素數，並檢查每個隨機數是否在該組中。這就是'filter_primes = primes（10_000_000）.intersection' - 像往常一樣調用'filter_primes（general_list）'。 – Ryan

這個怎麼樣？我認爲這是一個好一點：

def filter_primes(general_list): 
    return filter(is_prime, set(general_list))

這種方式，我們不叫is_prime()爲相同數量的多次。

來源

2017-07-02 14:54:46

Yeahhh，這有點幫助，謝謝！ – flpn

Eratosthenes的篩比試用部，你使用的方法更有效率。
您的審判部門循環可以變得更高效，花費大約一半的時間。兩個是唯一的偶數，所以把兩個視爲一個特殊情況，之後只處理奇數，這會使工作減半。

我的Python是不存在的，但是這應該僞代碼把事情說清楚：

def isPrime(num) 

    // Low numbers. 
    if (num <= 1) 
    return false 
    end if 

    // Even numbers 
    if (num % 2 == 0) 
    return (num == 2) // 2 is the only even prime. 
    end if 

    // Odd numbers 
    for (i = 3 to sqrt(num) + 1 step 2) 
    if (num % i == 0) 
     return false 
    end if 
    end for 

    // If we reach here, num is prime. 
    return true; 

end def

這step 2在for循環是什麼減半的工作。在先前已消除了所有甚至您只需使用奇試除數，以測試號碼：3，5，7，...

來源

2017-07-02 15:15:32 rossum

這個篩子是否與隨機數列表一起工作？ – flpn

這不是一個篩子，它只是測試提供的數字。如果你將它傳遞給相同的數字兩次，它將測試該數字兩次。一個篩子將計算每個數字的範圍，並在詢問時返回預先計算的結果。 – rossum

3輪的米勒羅賓測試（https://en.wikipedia.org/wiki/Miller%2dRabin_primality_test）使用鹼2,7，以及61，是已知的準確檢測所有素數< = 32位，即，任何適合python的東西。

如果數字很大，這比試劃或篩選要快得多。

如果數字不可能很大（即，如您在評論中所建議的那樣，< 10,000,000），那麼您可能需要預先計算所有質數的集合，但是其中有600,000個以上。

來源

2017-07-02 16:50:31

從Python中隨機數列表過濾素數的最有效方法

回答

相關問題