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

我怎样才能使我的代码更有效率并且能够更快地计算梅森素数。我想使用该程序找到任何可能的新完全数。

Answer 1

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 2

如果你只是想检查一个数是否是质数，那么你不需要找到它的所有因数。您已经知道 1 和 num 是因子。一旦你找到第三个因素，那么这个数字就不可能是素数。你在浪费时间寻找第四、第五等因素。

梅森数的形式为 2^n - 1，因此始终为奇数。因此它的所有因素都是奇数。如果您只寻找奇数因子，则可以将循环的运行时间减半：从 3 开始，然后第 2 步到下一个可能的因子。

因数成对出现，一个比平方根大，一个比平方根小。因此，正如@Francesco 的代码所示，您只需要查找直到平方根的因子。对于较大的梅森数，这可以为您节省大量时间。

将这两点放在一起，你的循环应该更像：

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

Answer 3

到目前为止显示的所有解决方案都使用了错误的算法，完全错过了梅森素数的点。梅森素数的优点是我们可以比像其他奇数那样通过蛮力更有效地测试它们的素性。我们只需要检查素数的指数并使用 Lucas-Lehmer primality test 来完成其余的工作：

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 的代码在 M7 524287 之后陷入困境，@FrancescoBarban 的代码在 M8 2147483647 之后陷入困境。以上代码在大约 15 秒内生成 M18！这是最多 M11，在大约 1/4 秒内生成：

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

这个程序在 M20 之上陷入困境，但它不是一个特别有效的实现。这简直是一个不错的算法。

python 中的高效梅森素数生成器

Efficient Mersenne prime generator in python

primes

python-3.x