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

完全数计算

https://www.nowcoder.com/practice/7299c12e6abb437c87ad3e712383ff84

#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;
}
全部评论

相关推荐

牛客383479252号:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务