完全数: 又称完美数,如果一个数恰好等于它的真因子之和,则称该数为“完全数”。第一个完全数是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

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

类似文章

发表回复