题解 | #完全数计算#

背景知识

完美数是除了自身外，所有真因子之和等于自身的自然数。
我们寻找完美数的方法就是遍历，只是可以通过以下特点，减少遍历次数：

1. 一个数的真因子一定小于等于自身的一半
2. 而由于真因子一定是成对出现的（除1*本身以外，我们只取1），所以我们只需要遍历2到之间的数即可找完所有真因子

代码如下：

import sys
for n in sys.stdin:
    n = int(n)
    count = 1           # 1是完美数且n>0，则最少有一个完美数

    # 遍历2到n之间的所有数
    for i in range(2, n):

        # 一个数的真因子只可能在1到该数的1/2之间，由于整除一次能找到两个真因子，故遍历1到该数的平方跟之间，一定能找完
        sub = 1         # sub为真因子之和，由于1一定是真因子，故初始为1
        for j in range(2, int(pow(i, 1/2))):
            if i % j == 0:        # 如果j能整除，则是j和整除的数字都是真因子
                sub += j + i/j

        if sub == i:
            count += 1

    print(count)