#3727. 完美数判定

完美数判定

题目描述

给定一个正整数 NN,请判断它是否为“完美数”。一个正整数如果是其所有真因子(即小于 NN 的约数)之和,则称其为完美数。

输入格式

输入一个正整数 NN (1≤N≤100001 \le N \le 10000)。

输出格式

如果是完美数输出 "YES",否则输出 "NO"。

样例

6
YES 
12
NO 

说明/提示

数据范围较小,可以使用循环遍历 11 到 N−1N-1。如果 NN 能被 ii 整除,则将 ii 累加到总和 sumsum 中。最后判断 sumsum 是否等于 NN。

解析

本题要求判断一个正整数 NN 是否为完美数。根据定义,若 NN 等于其所有真因子(小于 NN 的约数)之和,则 NN 为完美数。

解题思路 由于数据范围较小(N≤10000N \le 10000),我们可以采用最直观的枚举法。首先读取输入的整数 NN,初始化一个累加器 sum。然后,遍历从 11 到 N−1N-1 的每一个整数 ii。如果在遍历过程中发现 NN 能被 ii 整除(即 N%i==0N \% i == 0),说明 ii 是 NN 的一个真因子,将其累加到 sum 中。遍历结束后,比较 sum 的值是否等于 NN。如果相等,输出 "YES",否则输出 "NO"。

算法选择理由 该算法的时间复杂度为 O(N)O(N)。对于 NN 最大为 1000010000 的情况,循环次数仅为 10410^4 次。现代计算机在 1 秒内可以轻松处理 10810^8 级别的运算,因此 O(N)O(N) 的复杂度完全满足题目要求,且该算法逻辑简单,易于理解和实现。

复杂度分析

  1. 时间复杂度:O(N)O(N)。我们需要遍历 11 到 N−1N-1 的所有数,每个数的整除判断操作是 O(1)O(1) 的。
  2. 空间复杂度:O(1)O(1)。我们只使用了常数个变量(如 sum、i、n),不随输入规模增长。

来源

AI 生成 · 系统大模型(域):glm-4.7-flashx · 入门 · 数学