找出两万亿内所有完全数

完全数: 又称完美数，如果一个数恰好等于它的真因子之和，则称该数为“完全数”。第一个完全数是6，第二个完全数是28，第三个完全数是496，后面的完全数还有8128、33550336等等。比如：6有三个真因子1、2、3，而6=1+2+3。

需求：找出一定数字范围内所有完全数，如两万亿以内。

思路：如果使用暴力方法直接循环每一个数，找出它的真因子并判断真因子之和是否等于自身，那么复杂度相当高，就算只计算到百万级也会慢到爆。

这里引入一位天才级公式 – 欧拉公式：如果i是质数，2^i -1也是质数，那么（2^i-1）*2^(i-1)就是完全数。

import time


# 起始时间
start_time = time.perf_counter()

# 判断一个数是否为质数
def check_prime(n):
    if n == 1:
        return False
    lst = []
    for i in range(2, int(n / 2) + 1): # 只需要遍历到中位数即可
        if n % i == 0:
            lst.append(i)
    if not lst: # n没有其他真因子
        return True
    else:
        return False


num = 2000000000000  # 两万亿
res = []
for i in range(1, num + 1):
    if (2 ** i - 1) * 2 ** (i - 1) > num:
        break
    # 欧拉公式 - 如果i是质数，2^i-1也是质数，那么(2^i-1)*2^(i-1)就是完全数
    elif check_prime(i) and check_prime(2 ** i - 1):
        res.append((2 ** i - 1) * 2 ** (i - 1))
print(res)
# 结束时间
end_time = time.perf_counter()
print(f'程序执行时间：{end_time - start_time}')

--------------------------------------------------------
# [6, 28, 496, 8128, 33550336, 8589869056, 137438691328]
# 程序执行时间：0.008999100000000003

这种量级，程序执行时间是毫秒级，这应该是找完全数最快的一种方法了，没有之一。