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):