解题思路

  1. 完全数的定义：一个数等于它的所有真因子（除了自身以外的约数）之和

    • 例如：28的真因子有1,2,4,7,14，且1+2+4+7+14=28

  2. 实现思路：

    • 遍历1到 的每个数
    • 对每个数找出其所有真因子
    • 判断真因子之和是否等于该数本身
    • 统计满足条件的数的个数

  3. 优化：

    • 只需要遍历到 就可以找到所有因子
    • 已知的完全数很少，可以直接判断

代码

#include <iostream>
using namespace std;

bool isPerfectNumber(int num) {
    if (num <= 1) return false;
    int sum = 1;  // 1总是因子
    // 只需要遍历到sqrt(num)
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            sum += i;
            if (i * i != num) {  // 避免平方数重复计算
                sum += num / i;
            }
        }
    }
    return sum == num;
}

int main() {
    int n;
    while (cin >> n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isPerfectNumber(i)) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static boolean isPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 1;  // 1总是因子
        // 只需要遍历到sqrt(num)
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {  // 避免平方数重复计算
                    sum += num / i;
                }
            }
        }
        return sum == num;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int count = 0;
            for (int i = 1; i <= n; i++) {
                if (isPerfectNumber(i)) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

def is_perfect_number(num):
    if num <= 1:
        return False
    sum_factors = 1  # 1总是因子
    # 只需要遍历到sqrt(num)
    i = 2
    while i * i <= num:
        if num % i == 0:
            sum_factors += i
            if i * i != num:  # 避免平方数重复计算
                sum_factors += num // i
        i += 1
    return sum_factors == num

while True:
    try:
        n = int(input())
        count = 0
        for i in range(1, n + 1):
            if is_perfect_number(i):
                count += 1
        print(count)
    except EOFError:
        break

算法及复杂度

  • 算法：试除法找因子
  • 时间复杂度： - 需要遍历1到n的每个数，每个数需要的时间找因子
  • 空间复杂度： - 只使用了常数额外空间