寻找十全十美数 Python

什么是十全十美数

十全十美数是指一个数的真约数之和等于它本身，真约数是指一个数除了本身以外所有的因子。

def perfect_number(num):
    factors_sum = sum([i for i in range(1, num) if num % i == 0])
    return factors_sum == num

如何找到十全十美数

要找到十全十美数，我们可以使用上面的代码，一个一个数地判断。但这样十分耗时，我们可以优化算法。

根据文献介绍，形如 $2^{p-1} * (2^p-1)$ 的数是梅森素数，当且仅当 $2^p-1$ 是质数。由于目前已知的最大质数是 $2^{82,589,933}-1$，所以当 $p>82,589,933$ 时，梅森素数个数为零。而梅森素数对应的十全十美数即为 $2^{p-1} * (2^p-1)$。

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True

def perfect_number(num):
    factors_sum = sum([i for i in range(1, num) if num % i == 0])
    return factors_sum == num

perfect_numbers = []
for p in range(2, 82589934):
    if is_prime(2**p-1):
        perfect_numbers.append(2**(p-1)*(2**p-1))

十全十美数的规律

除了梅森素数对应的十全十美数，其他十全十美数的个数较少，前几个数分别为 6、28、496、8128。这些数的规律是它们都是偶完全数，偶完全数的定义是一个数的所有因子相加等于它本身的两倍。

def perfect_number(num):
    factors_sum = sum([i for i in range(1, num) if num % i == 0])
    return factors_sum == 2*num

perfect_numbers = []
for num in range(2, 100000):
    if perfect_number(num):
        perfect_numbers.append(num)

十全十美数的应用

十全十美数在密码学中有应用，其中的一个例子是 RSA 加密算法。RSA 需要选择两个大质数，根据这两个质数计算出 N，找到两个与 N 互质的数 e 和 d，最后把 N 和 e 公开，而 d 则保密。RSA 的安全性基于破解者不可能通过已知的公开信息 N 和 e 来计算出 d。RSA 的实际工作中使用的是更大的质数和更复杂的算法，但十全十美数仍然是其中的基础。