把寻找完全数的python程序改为寻找梅森素数的python程序

Question

我想要把一个寻找完全数的python程序改为寻找梅森素数(可以表示为2^n-1形式的素数)的python程序，请问要如何修改
源码如下:

import datetime
def isPrime(N):
    if N < 4: return N > 1
    if ((N & 1) == 0): return False
    i = 3
    while i * i <= N :
        if (N % i) == 0 : return False
        i += 2
    return True
def primality(N, M):
    if N == 2 : return True
    s = 4
    for i in range(0, N - 2) :
        s = (s * s - 2) % M
    return s == 0
def findPerfectNumber() :
    count = 0
    begin = datetime.datetime.now()
    strContent = ""
    for i in range(2,2000):
        M = (1 << i) - 1
        t = M << (i-1)
        # 当p为素数且梅森数2^p-1为素数时2^(p-1)*(2^p-1)为完全数
        if isPrime(i) and primality(i,M) :
            count += 1
            numLen = len(str(t))
            strContent = strContent + "第" + str(count) + "个" + str(numLen) + "位数：" + str(t) + "\r\n"
    end = datetime.datetime.now()
    print(strContent)
    print("FindPerfectNumber运行花费时间为:", (end - begin).total_seconds(), "s")
findPerfectNumber()

希望能提出一些建议，非常感谢
如果谁有更快筛选梅森素数的算法，也期望能够分享一下

Answer 1

需要修改两处：

程序输出内容：在输出时，将"第" + str(count) + "个" + str(numLen) + "位数：" + str(t) + "\r\n" 改为 "第" + str(count) + "个梅森素数：" + str(M) + "\r\n"。

循环体内部的判断逻辑：将 "if isPrime(i) and primality(i,M) :" 改为 "if isPrime(M) :"，即只判断2^n-1的值是否是素数。

import datetime
def isPrime(N):
    if N < 4: return N > 1
    if ((N & 1) == 0): return False
    i = 3
    while i * i <= N :
        if (N % i) == 0 : return False
        i += 2
    return True
def findMersennePrime() :
    count = 0
    begin = datetime.datetime.now()
    strContent = ""
    for i in range(2,2000):
        M = (1 << i) - 1
        # 只判断2^n-1的值是否是素数
        if isPrime(M) :
            count += 1
            strContent = strContent + "第" + str(count) + "个梅森素数：" + str(M) + "\r\n"
    end = datetime.datetime.now()
    print(strContent)
    print("FindMersennePrime运行花费时间为:", (end - begin).total_seconds(), "s")
findMersennePrime()