完美合数C++欧拉筛

完美合数是指除了1和它本身之外的所有因数之和也恰好等于这个数本身的正整数。例如6是一个完美合数，因为1 + 2 + 3 = 6。在C++中，欧拉筛（Euler's Sieve）是一种高效的算法用于找出所有小于一定范围内的质数，这可以作为计算完美合数的基础。

下面是一个简单的C++实现思路：

1. 首先创建一个布尔数组isPrime，大小为n+1，其中isPrime[i]表示i是否是质数。初始全部设为true，只有1标记为false。
2. 使用欧拉筛算法遍历数组，对于每个质数p，将它的倍数（从p²开始，每次加p）标记为非质数。这是因为如果一个数有质数p作为因子，那么它的所有倍数也将有相同的因子，无需再检查。
3. 遍历结束后，对于每一个未被标记为非质数的数n，计算其所有因数（包括1和n）的和，如果这个和等于n，就找到了一个完美合数。

#include <vector>
using namespace std;

void printPerfectNumbers(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    for (int num = 2; num <= n; ++num) {
        if (isPrime[num] && sumOfFactors(num, num) == num) {
            cout << num << " ";
        }
    }
}

// 计算一个数及其因数的总和
long long sumOfFactors(int num, int sqrtNum) {
    long long sum = 1;
    for (int i = 2; i <= sqrtNum; ++i) {
        if (num % i == 0) {
            sum += i;
            if (i != num / i) { // 如果不是平方根，还需要加上另一个因子
                sum += num / i;
            }
        }
    }
    return sum;
}

int main() {
    int limit = 10000; // 可调整范围，查找完美合数
    cout << "Perfect numbers below " << limit << ": ";
    printPerfectNumbers(limit);
    return 0;
}