题解 | #完全数计算#分解质因数方法求解O(nlogn)

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 2; i <= n; i++)
    {
        int a = i;
        //分解质因子
        unordered_map<int, int> primes;
        for(int j = 2; j <= a / j; j++)
            while(a % j == 0)
            {
                a = a / j;
                primes[j]++;
            }
        if(a > 1) primes[a]++;

        //求出所有约数的和
        int sum = 1;
        for(auto prime : primes)
        {
            int p = prime.first, m = prime.second;
            int t = 1;
            while(m--) t = (t * p + 1);
            sum *= t;
        }
        sum -= i; //除去自身
        //cout << sum << endl;
        if(sum == i) ans++;
    }
    cout << ans << endl;

    return 0;
}