扩展测试值范围时无返回值

Question

我编写了一个程序来查找 Mersenne 素数，它工作正常，除非我将测试值的范围扩展到 61 以上。

例如，如果我想测试 100 个数字以查看它们是否为素数，Idle 只会显示一个空白屏幕。我可以手动将更大的值放入中间块，所以我不知道这只是列表的限制（附加的数字太长）还是 61 是一个神奇的数字。

编辑：看来问题可能与内存使用有关，因为程序保持运行但从来没有 returns 任何东西。

Mersenne = []

for i in range(1,61):
    t = (2 ** i) - 1
    Mersenne.append(t)

prime = []
testedValues = [1]

for i in Mersenne:
    passFail = []
    while 1 not in passFail:
        for t in range(2, i):
            if t > (i/testedValues[-1]):
                break
            if i % t == 0:
                passFail.append(1)
                break
            testedValues.append(t)
        if 1 not in passFail:
            prime.append(i)
            break


failed = []
passed = []

for i in Mersenne:
    if i not in prime:
        failed.append(i)
    elif i in prime:
        passed.append(i)

print('Failed: \n', failed,"\n")
print('Passed: \n', passed)

Answer 1

你的程序的问题是它使用了错误的算法。如果有足够的时间，它最终应该产生 p = 61 的结果。但是，该数字是 2305843009213693951 并且您的素数检查效率低下，因为它检查从 2 到 n 的每个除数，而不是仅检查奇数到 sqrt(n)。然而，这仍然不够。

潜在梅森素数的全部意义在于我们可以比像其他奇数那样使用蛮力更有效地测试它们的素性。添加 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

Mersenne = [3]
prime = [3]

for i in range(3, 1000):
    t = (2 ** i) - 1
    Mersenne.append(t)

    if Lucas_Lehmer(i):
        prime.append(t)

failed = []

for number in Mersenne:
    if number not in prime:
        failed.append(number)

print('Failed:\n', failed, "\n")
print('Passed:\n', prime)

结果要好得多，例如：

Passed:
 [3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727, 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151, 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127]

扩展测试值范围时无返回值

No value returned when range of tested values extended

python

primes

python-3.x