题目分析

1. 题目给出我们若干数字
2. 对于每个数字，从0到当前数字为止，统计其中完全数的个数，输出对应的每一个统计结果
3. 完全数的定义为：该数字若所有因子（除去该数字本身）之和为该数字，则该数字为完全数

方法一：统计所有因子

• 实现思路
  • 对于给出的数字n，通过perfectNum函数判断每一个数字是否为完全数
  • 判断的方式是根据完全数的定义来的，对某个数字进行除本身之外的因子统计，如果和为数字本身，则计数一次
  • 最终输出统计的结果即可

def perfectNum(n):                # 判断是否是完全数
    nums = [1]                    # 1一定是一个因子
    i = 2
    while i*i <= n:               # 尝试因子迭代直到根号n为止
        if n % i == 0:            # 添加因子到nums组中
            nums.append(i)
            nums.append(n/i)
        i += 1
    if sum(nums) == n:            # 判断是否符合完全数的规则
        return 1
    return 0

def count(n):                    # 统计完全数的个数
    res = 0
    for i in range(2,n+1):
        res += perfectNum(i)
    return res


while True:
    try:
        m = int(input())
        print(count(m))
    except:
        break
        

复杂度分析

• 时间复杂度：$O({\sum }_{i=1}^m{n}_i^2)O(\backslash sum\_\{i=1\}^\{m\}\{n\_i^2\})$，对于每一个数字n，都需要$n^{2}n^2$的时间代价，一重循环的时间开销在统计n以内数字个数的阶段，另一重循环的开销在对于数字本事是否为完全数的时间开销上
• 空间复杂度：$O(n)O(n)$，储存因子的数组空间开销

方法二：公式法

• 实现思路
  • 欧拉曾推算出完全数的获得公式：如果$pp$是质数，且$2^p-12^p-1$也是质数，那么$\mathrm{（}{2}^p-1\mathrm{）}\cdot 2^{p-1}（2^p-1）·2^\{p-1\}$便是一个完全数。
  • 因此对于一个数$ii$，我们要判断$ii$和$2^i-12^i-1$都要是质数才可以确定$\mathrm{（}{2}^i-1\mathrm{）}\cdot 2^{i-1}（2^i-1）·2^\{i-1\}$
  • 统计计数结果即可

def isPrime(n):                    # 判断是否为素数
    i = 2
    while i*i <= n:                # 对自然数进行遍历，判断是否是n的因子
        if n % i == 0:
            return False
        i += 1
    return True

def isPerfect(n):
    i = 2
    count = 0
    while i*i <= n:                          # 对自然数进行遍历
        j = pow(2, i) - 1                    # 公式中第二部分的计算
        perfectNum = pow(2, i-1) * j         # 理论上推导的完全数结果
        if perfectNum <= n:                  # 由于上限是n要添加判断
            if isPrime(i) and isPrime(j):    # 根据欧拉推导的完全数判别定理进行判断
                count += 1                   # 统计计数
        i += 1
    return count

while True:
    try:
        n = int(input())                        # 转化成int类型，否则默认输入类型为str
        print(isPerfect(n))
    except:
        break

复杂度分析

• 时间复杂度：$O({\sum }_{i=1}^m{n}_i^2)O(\backslash sum\_\{i=1\}^\{m\}\{n\_i^2\})$，对于每一个数字n，都需要$n^{2}n^2$的时间代价，一重循环的时间开销在遍历n以内的自然数来作为质数判断的待定数上，另一重循环的开销在判断公式中两个条件是否满足上
• 空间复杂度：$O(1)O(1)$，没有用额外空间开销