Python中的高效梅森素數生成器

Question

我編寫了一個看起來效率不高的代碼。它只計算一些素數。

這是我的代碼：

num=float(1) 
a=1 

while(num>0): # Create variable to hold the factors and add 1 and itself (all numbers have these factors) 
    factors = [1, num] 

    # For each possible factor 
    for i in range(2, int(num/4)+3): 
     # Check that it is a factor and that the factor and its corresponding factor are not already in the list 
     if float(num) % i == 0 and i not in factors and float(num/i) not in factors: 
      # Add i and its corresponding factor to the list 
      factors.append(i) 
      factors.append(float(num/i)) 
    num=float(num) 
    number=num 
# Takes an integer, returns true or false 
    number = float(number) 
# Check if the only factors are 1 and itself and it is greater than 1 
    if (len(factors) == 2 and number > 1): 
     num2=2**num-1 
     factors2=[1, num] 
     for i in range(2, int(num2/4)+3): 
     # Check that it is a factor and that the factor and its corresponding factor are not already in the list 
      if float(num2) % i == 0 and i not in factors2 and float(num2/i) not in factors2: 
      # Add i and its corresponding factor to the list 
       factors2.append(i) 
       factors2.append(float(num2/i)) 
     if(len(factors2)==2 and num2>1): 
      print(num2) 
     a=a+1 
    num=num+2 

我怎樣才能讓我的代碼更高效，並能計算出Mersenne數的更快。我想使用該程序來查找任何可能的新完美數字。

Answer 1

所有迄今所示的解決方案使用壞的算法，失蹤梅森點素數完全。梅森素數的優勢是我們可以像其他奇數那樣通過強力測試來更有效地測試它們的素數。我們只需要檢查primeness指數，並使用Lucas-Lehmer primality test做休息：M7 524287後@下來

def lucas_lehmer(p): 
    s = 4 
    m = 2 ** p - 1 
    for _ in range(p - 2): 
     s = ((s * s) - 2) % m 
    return s == 0 

def is_prime(number): 
    """ 
    the efficiency of this doesn't matter much as we're 
    only using it to test the primeness of the exponents 
    not the mersenne primes themselves 
    """ 

    if number % 2 == 0: 
     return number == 2 

    i = 3 
    while i * i <= number: 
     if number % i == 0: 
      return False 
     i += 2 

    return True 

print(3) # to simplify code, treat first mersenne prime as a special case 

for i in range(3, 5000, 2): # generate up to M20, found in 1961 
    if is_prime(i) and lucas_lehmer(i): 
     print(2 ** i - 1) 

的OP代碼沼澤FrancescoBarban代碼M8 2147483647後停滯不前上面的代碼中大約產生M18 15秒！這裏是給M11，在大約1/4秒產生：

3 
7 
31 
127 
8191 
131071 
524287 
2147483647 
2305843009213693951 
618970019642690137449562111 
162259276829213363391578010288127 
170141183460469231731687303715884105727 
6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 
531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 

這項計劃停滯不前上述M20，但它不是一個格外有效的實現。這根本不算錯誤的算法。

Answer 2

import math 

def is_it_prime(n): 

    # n is already a factor of itself 
    factors = [n] 

    #look for factors 
    for i in range(1, int(math.sqrt(n)) + 1): 

     #if i is a factor of n, append it to the list 
     if n%i == 0: factors.append(i) 
     else: pass 

    #if the list has more than 2 factors n is not prime 
    if len(factors) > 2: return False 
    #otherwise n is prime 
    else: return True 

n = 1 
while True: 

    #a prime P is a Mersenne prime if P = 2^n - 1 
    test = (2 ** n) - 1 

    #if test is prime is also a Mersenne prime 
    if is_it_prime(test): 
     print(test) 
    else: pass 
    n += 1 

可能會堅持到2147483647，但你知道，下一個梅森素數是2305843009213693951 ...所以，如果它需要比你預期更多的時間不要擔心;）

Answer 3

如果你只是想要檢查一個數字是否是總數，那麼你不需要找出所有的因素。你已經知道1和num是因素。只要你找到第三個因素，那麼這個數字就不能是素數。你正在浪費時間尋找第四，第五等因素。

梅森數是2^n - 1的形式，所以總是奇數。因此所有因素都是奇怪的。如果您只查找奇怪的因素，則可以將循環的運行時間減半：從3開始，到步驟2開始下一個可能的因子。

因素是成對出現的，一個大於平方根，另一個小於一個。因此，您只需要查找平方根即可，正如@ Francesco的代碼所示。這可以爲您節省大量梅森數字的時間。

把這兩點在一起，你的循環應該更像：

#look for factors 
for i in range(3, int(math.sqrt(n)) + 1, 2):