求正整数2和n之间的完全数

题目描述

求正整数 2 和 n 之间的完全数，一行一个按升序。完全数指真因子（含 1、不含自身）之和等于它本身的自然数，例如 $6 = 1 + 2 + 3$ 。输入一个整数 $n\ (n \leqslant 1000)$ ；输出一行一个数。样例输入 7 输出 6。

思路

对每个 $i \in [2, n]$ ，用试除法累加真因子之和：因子成对出现，只枚举 $d \in [2, \sqrt{i})$ 把 $d$ 与 $i/d$ 一起加，再单独处理完全平方数的 $\sqrt{i}$ 一次；和等于 $i$ 就输出。复杂度 $O(n\sqrt{n})$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 21:03
# update_at: 2026-09-30 09:15

import sys


def perfect_upto(n: int) -> list[int]:
    """返回 [2, n] 内的全部完全数，从小到大。

    n ≤ 1000，直接枚举每个 i，用试除法累加真因子：成对枚举 d 与 i//d，
    每个数只试到 √i，总代价 O(n√n)，与 std.cpp 同阶。
    """
    ans: list[int] = []
    for i in range(2, n + 1):
        s = 1                                    # 1 是所有 i ≥ 2 的真因子，先记上
        d = 2
        while d * d < i:                         # d < √i 时补上成对因子 (d, i//d)
            if i % d == 0:
                s += d + i // d
            d += 1
        if d * d == i:                            # i 恰为完全平方数，√i 只算一次
            s += d
        if s == i:
            ans.append(i)
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 上界 n
    print('\n'.join(map(str, perfect_upto(n))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:32
 * update_at: 2026-10-05 03:32
 */

#include <iostream>
using namespace std;

typedef long long ll;

// 判断 i 是否为完全数：真因子之和是否等于 i
// 利用因子成对性，只枚举 d ∈ [2, √i)，把 d 和 i/d 一起累加
bool is_perfect(int i) {
    int s = 1; // 1 一定是真因子，先记上
    int d = 2;
    while ((ll)d * d < i) {
        if (i % d == 0) {
            s += d + i / d;
        }
        d++;
    }
    // 完全平方数的平方根因子要单独加一次：循环结束时 d = ⌊√i⌋+1
    d--; // 回到最后一个满足 d*d <= i 的 d
    if ((ll)d * d == i) {
        s += d;
    }
    return s == i;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n; // 上界 n

    // 枚举 [2, n]，按升序输出所有完全数
    for (int i = 2; i <= n; i++) {
        if (is_perfect(i)) {
            cout << i << "\n";
        }
    }

    return 0;
}

求正整数2和n之间的完全数

目录

题目描述

思路

参考代码