C++ 中的亏数

亏数 是一个正整数，其真因子（不包括数字本身）之和小于该数字。例如，8 是亏数，因为它的因子（1、2、4）之和为 7，小于 8。

输入 10

输出: 亏数

输入 12

输出: 不是亏数

说明

对于数字 10，其真因子是 1、2 和 5。将它们相加得到 8，小于 10，因此 10 是一个亏数。对于 12，其真因子是 1、2、3、4 和 6，总和为 16，大于 12，所以 12 不是亏数。

方法 1：使用因子和比较

算法：如果一个数字是亏数

步骤 1：理解问题： 明确目标：检查给定数字 n 是否为亏数。为此，计算其真因子之和并与 n 进行比较。如果和小于 n，则该数字是亏数。

步骤 2：定义亏数： 亏数是一个正整数，其真因子（不包括数字本身）之和小于该数字。真因子是所有小于该数字且能被其整除的整数，不包括数字本身。例如，8 是亏数，因为其因子（1、2、4）之和为 7，小于 8。

步骤 3：输入数字： 从输入数字 n 开始。此数字应为正整数，因为亏数只对正整数定义。

步骤 4：初始化变量： 设置一个变量 sum 来存储因子的累积总和。在开始因子计算之前，将 sum 初始化为 0。

步骤 5：查找真因子： 数字的真因子是所有小于 n 且能被 n 整除（余数为 0）的整数。遍历从 1 到 n-1 的所有整数。

对于每个数字 i，检查 n mod i = 0（即 i 能整除 n，无余数）是否成立。如果为真，则将 i 添加到 sum 中。

步骤 6：计算因子和： 循环结束时，sum 将保存 n 的所有真因子的总和。

步骤 7：将和与 n 进行比较： 如果 sum < n，则 n 是亏数，因为其真因子之和小于 n。否则，n 不是亏数。

步骤 8：输出结果： 根据比较结果打印结果：“亏数”如果 sum < n。否则，“不是亏数”。

算法：如果一个数字不是亏数

步骤 1：理解问题： 如果一个数字的真因子（不包括数字本身）之和大于或等于该数字，则该数字不是亏数。任务是检查给定数字 n 是否满足此条件。

步骤 2：输入数字： 将正整数 n 作为输入。只有正整数才有效。

步骤 3：初始化变量： 设置一个变量 sum 来累加真因子的总和。将其初始化为零：sum=0

步骤 4：识别真因子： 真因子是所有小于 n 且能被 n 整除的整数，没有余数。使用循环遍历从 1 到 n-1 的数字。

对于每个数字 i，检查 n mod i = 0 是否成立。如果条件为真，则 i 是一个真因子。将 i 添加到 sum 中。

步骤 5：计算因子和： 循环完成后，sum 将保存 n 的所有真因子的和。

步骤 6：将 sum 与 n 进行比较： 如果 sum ≥ n，则数字 n 不是亏数，因为其因子足够或超过 n。如果 sum < n，则该数字是亏数。

步骤 7：输出结果： 显示结果：“不是亏数”如果 sum ≥ n。“亏数”否则。

程序

输出

10 is Deficient
12 is Not Deficient   

复杂度分析

时间复杂度

确定一个数字是否为亏数的时间复杂度 为 O(n)，其中 n 是输入数字。这是因为我们需要检查从 1 到 n-1 的每个整数以找到因子。因此，该过程涉及迭代到 n。

空间复杂度

确定一个数字是否为亏数的空间复杂度 为 O(1)，因为算法只需要固定量的额外空间。它使用一个单独的变量来求和因子，并且不存储任何大型数据结构，无论输入大小如何。

方法：高效因子计算（使用 √n）

上述方法遍历从 1 到 n-1 的所有数字以查找真因子，其时间复杂度为 O(n)。一种更有效的方法可以通过成对考虑因子并仅迭代到 n\sqrt{n}n 来降低此复杂度。