题目描述
记 为
的所有真约数（小于
且整除
的正整数）之和。如果
，且
，那么
和构成一个
亲和数对，
和
被称为亲和数。
求所有小于 的亲和数的和。
思路
欧拉筛求解素因子和
因子和公式
代码
// 素数筛算法求解因子和问题
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 10000;
int prime[N + 5];
int f[N + 5];
int cnt[N + 5]; // cnt[i] 记录 i 最小素因子的幂次
void init() {
for (int i = 2; i <= N; i++) {
if (!prime[i]) {
prime[++prime[0]] = i;
f[i] = i + 1;
cnt[i] = 1;
}
for (int j = 1; j <= prime[0] && prime[j] * i < N; j++) {
prime[prime[j] * i] = 1;
if (i % prime[j]) { // i 与 prime[j] 互素
f[i * prime[j]] = f[i] * f[prime[j]];
cnt[i * prime[j]] = 1;
}
else {
f[i * prime[j]] = f[i] / (pow(prime[j], cnt[i] + 1) - 1) * (pow(prime[j], cnt[i] + 2) - 1); // 等比数列求和公式
cnt[i * prime[j]] = cnt[i] + 1;
break;
}
}
}
}
int main() {
init();
for (int i = 2; i < N; i++) f[i] -= i;
int ans = 0;
for (int i = 2; i < N; i++) {
if (f[i] != i && f[f[i]] == i) {
ans += i;
printf("%d %d\n", i, f[i]);
}
}
printf("%d\n", ans);
return 0;
}
