Python | 列出完数的二三事

太长不看版

原题

参考答案

import math


def is_perfect(number):
    result, numbers = False, []
    for j in range(2, int(math.sqrt(number)) + 1):
        if (number % j) == 0:
            numbers.append(j)
            if j * j != number:
                numbers.append(number / j)
    if numbers:
        if int(sum(numbers)) + 1 == number:
            result = True
    return result


try:
    listed, string = [], ""
    for cycle_ip in range(2, 10001, 2):
        if is_perfect(cycle_ip):
            listed.append(cycle_ip)
    while True:
        in_put, out_put = int(input()), ""
        for num in listed:
            if num <= in_put:
                out_put += str(num) + " "
        print("{}: {}".format(in_put, out_put.strip()) if out_put else "{}: NULL".format(in_put))
except EOFError:
    pass

代码思路

import math


def is_perfect(number):  # 函数：判断输入的参数 number 是否为完数
    result, numbers = False, []  # 减少 if 数量，用 sign 标记输出的结果。初始化一个列表numbers，用来存储所有因子
    for j in range(2, int(math.sqrt(number)) + 1):  # 遍历查找因子，通过开平方 +1 减少运算量；起点不包括一
        if (number % j) == 0:
            numbers.append(j)  # 这个是因子
            if j * j != number:  # 防止因子重复，如 8*8=64 这种情况
                numbers.append(number / j) # 计算出另一个因子并加入列表
    if numbers:
        if int(sum(numbers)) + 1 == number:  # 列表求和判断是否仍然为 number
            result = True  # 是的话把返回值设置成 True
    return result  # 如果第上一行行执行了，返回 True，若未执行，不是完数，返回 False（代码第五行预先定义了）


try:
    listed, string = [], ""  # listed：10000 以内的列表，string： 输出的值
    # 预先计算 1000 以内的列表，减少反复运算导致的卡顿
    for cycle_ip in range(2, 10001, 2):
        if is_perfect(cycle_ip):
            listed.append(cycle_ip)  # 将完数插入列表
    while True:  # 因为没有说明输入的组数，直接给无限循环
        # PTA 内所有 python 题都是如此，得到需要的结果后程序将正常退出
        in_put, out_put = int(input()), ""
        # 之后我们的值直接往 listed 里找即可
        for num in listed:
            if num <= in_put:
                out_put += str(num) + " "  # 因为要的结果的形式是 10000: 6 28 496 8128，我们先把冒号右边的内容存进变量
        print("{}: {}".format(in_put, out_put.strip()) if out_put else "{}: NULL".format(in_put))  # 格式化
except EOFError:  # 避免什么都没有输入就按回车的情况
    pass

故事模式

新的作业——普通的一天

大概是非常普通的一天，Python 老师非常普通的发布了一个新的作业，我也开始非常普通地做题。

首先是第一题：大菲波数，要求输出斐波那契数列，也就是兔子数列的某一项，思路花了一丢丢时间，简单完成；然后是第二题，素数判断，看到这里我又是一阵意想不到的狂喜（误），因为在此之前已经布置了好多次类似的作业了——Ctrl+C 然后 Ctrl+V，光速完成提交，持续了片刻的胸有成竹在四个大字——运行超时前顷然崩塌。

在蒙圈的状态下，我仔细重新看了一遍题目——时间限制：400 ms，原来如此——这道题目其实在检验程序的运行效率。思考片刻的我无果求助百度，终于得到了解答：引入 math 库对循环总次数开方+1，减少循环的次数，提高运行效率，一提交——成了！我心中大概是沾沾自喜的，此时我还没有意识到事情的严重性——直到我点开下一题：列出完数。

新的概念——完数

题目本身是有给完数的定义的，完数是一个正整数，该数恰好等于其所有不同真因子之和。例如，6、28是完数，因为6=1+2+3，28=1+2+4+7+14；而24不是完数，因为24≠1+2+3+4+6+8+12＝36。只是略微思索，我的手就开始在键盘上飞舞起来：

def is_perfect(number):
    flag, numbers, result = False, [], 0  # flag：将要返回的信息，numbers：初始化列表，result=所有因子之和
    for j in range(1, number):  # 第一次循环，遍历所有数字查找因子
        if (number % j) == 0:
            numbers.append(j)  # 通过循环将所有因子加入列表 numbers
    if numbers:
        for element in numbers:
            result += element  # 计算因子之和
        if result == number:  # 所有因子和相等则返回 True
            flag = True
    return 1 if flag else 0


try:
    listed, string = [], ""
    for cycle_ip in range(2, 10000):  # 先初始化一个默认列表，遍历 10000 以内的数字查找完数
        if is_perfect(cycle_ip):  # 这里是优化过的写法
            listed.append(cycle_ip)  # listed 就是 10000 内的完数的列表
    in_put = int(input())  # 输入 0，100，10000等
    out_put = ""
    for num in listed:  # 在 listed 内查找范围内的结果
        if num <= in_put:
            out_put += str(num) + " "
    print("{}: {}".format(in_put, out_put.strip()) if out_put else "{}: NULL".format(in_put))
except EOFError:
    pass

（写到这里我突然发现了代码算法可以进一步优化 ：/ ）

我，Still 胸有成竹，马上到 PTA 提交自己的答案，毫不意外...运行超时。之后发现，这道题限定在 1000ms 内运行完成，否则判 0分。那么此处就跳过我的内心活动。在百度上窜下跳后我终于找到了正解（附于文章末尾）。这里先跳过，讲讲这道题的正确思路。

再次优化——效率问题

上面的代码可以运行了，但是效率过低，要优化的话我们必须知道完数都是偶数，因此循环过程可以直接跳过所有奇数，而且我之前写代码的时候还不知道list，也就是列表，可以用sum求和...经过一丢丢简化，代码变成这个样子：

def is_perfect(number):
    sign, numbers = False, []  # 返回的结果变量名改成了sign，知道 sum 函数之后，result 完全没有存在的必要了
    for j in range(1, number):
        if (number % j) == 0:
            numbers.append(j)
    if numbers:
        if sum(numbers) == number:
            sign = True
    return sign


try:
    listed, string = [], ""
    for cycle_ip in range(2, 10001, 2):  # 完数都是偶数，直接跳着找，步长设置为 2
# 后略

到这里运行效率已经大大大大大大提升，然而还是会运行超时。这里我们要在完数判断的地方下功夫：找到一个因子，我们用数字除以这个因子可以得到另一个因子，减少计算量——那么我们要引入 math 对循环的次数开方并加 1：

for j in range(1, int(math.sqrt(number)) + 1):
    if(number % j) == 0:
        numbers.append(j)
        numbers.append(number / j)

但是这样可能会把同一个数字两次加入列表，我们可以加一个简单的判断：

if (number % j) == 0:
    numbers.append(j)
    if j * j != number:
        numbers.append(number / j)

这里运行一下发现列表输出了 NULL，通过 print(sum(numbers), number) 发现 sum 计算出的结果是浮点书，这里我们直接强制转换为 int。（print 是非常重要的找 bug 手段）

# print(int(sum(numbers)), number)
if numbers:
    if int(sum(numbers)) == number:

然而修改之后还是有问题。这里我直接输出 number 为 6 时的因子列表看看是怎么回事：

代码
if number==6:
    print(numbers)
# print(int(sum(numbers)), number)
输出
[1, 1, 6.0, 2, 3.0]

显而易见，计算过程中错误地把数字本身也加进去了，这里我们可以①再做一层判断；②调整循环起点：

# ①再做一层判断
        if (number % j) == 0:
            numbers.append(j)
            if j * j != number:
                result = number / j
                if result != number:
                    numbers.append(result)
    
# ②调整循环起点
    for j in range(2, int(math.sqrt(number)) + 1):
        if (number % j) == 0:
            numbers.append(j)
            if j * j != number:
                numbers.append(number / j)

此时，完成的代码如下：

import math


def is_perfect(number):
    sign, numbers = False, []  # 知道 sum 函数之后，result 完全没有存在的必要了
    for j in range(2, int(math.sqrt(number)) + 1):
        if (number % j) == 0:
            numbers.append(j)
            if j * j != number:
                numbers.append(number / j)
    if numbers:
        if int(sum(numbers)) == number:
            sign = True
    return sign


try:
    listed, string = [], ""
    for cycle_ip in range(2, 10001, 2):  # 完数都是偶数，直接跳着找
        if is_perfect(cycle_ip):
            listed.append(cycle_ip)
    in_put, out_put = int(input()), ""
    for num in listed:
        if num <= in_put:
            out_put += str(num) + " "
    print("{}: {}".format(in_put, out_put.strip()) if out_put else "{}: NULL".format(in_put))
except EOFError:
    pass

此时的我信心满满的把这串代码扔进 PTA ——答案错误？？？仔细一看，原来是漏了一个题目要求：测试数据有多组，处理到文件尾。对于不明确有多少组数据的题目，我们直接给个while True。

while True:
    in_put, out_put = int(input()), ""
    for num in listed:
        if num <= in_put:
            out_put += str(num) + " "
    print("{}: {}".format(in_put, out_put.strip()) if out_put else "{}: NULL".format(in_put))

程序终于安全通关。完整代码见文章开头。

超时问题——代码量

写完代码当天，只有我和上帝能看懂；过了几天，只有上帝能看懂了...
我看不懂，但我大受震撼.jpg

我的某一个朋友提出疑问：代码量这么多没有超时吗？是否超时其实取决于计算量，有时候即使代码量很少但程序会卡死，比如说斐波那契数列的递归写法就是一个很好的例子。（其实做题目的时候我还不知道有递归，用单纯计算的方法计算，恰恰避开了遍历次数过多卡死的情况）。有时候大量的代码，就是为了减少计算量。当然，这也不是说代码量越多越好。

附录：大受震撼——骗过系统

在我以为代码也就这么几个写法时，总有同学的骚操作让我眼前一黑。这个骚操作能够达成的前提是，PTA 只要求输出正确的结果，你的代码长啥样并不管，于是就有了我同学的新奇操作：既然我们知道10000 以内的完数有6、28、496、8128，那么我们直接在代码里写死输出的结果就行了：

try:
    while True:
        number = int(input())
        if number < 6:
            string = "NULL"
        elif 6 <= number < 28:
            string = "6"
        elif 28 <= number < 496:
            string = "6 28"
        elif 496 <= number < 8128:
            string = "6 28 496"
        else:
            string = "6 28 496 8128"
        print("{}: {}".format(number, string))
except EOFError:
    pass

完 全 正 确

说真的我真的没想到有这种解决方式...那这种写法可以不可以呢？从系统角度来看，这种写法当然是可以的，想要的结果完全正常输出；从学习编程的角度来说，这样完全起不到检验能力的效果；但是如果是生产环境，这个方法反而很好的解决了运行效率的问题。（正常代码运行需要41ms，这种骚操作只需要17ms！）这样写可以大大提高程序运行的效率。

那么这次就到这里，再会~