题解 | #完全数计算#分解质因数方法求解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; }