欧拉计划 23

Non-abundant sums

题目描述

记 为 的所有真约数（小于 且整除 的正整数）之和。
若 ，则称之为亏数；反之，则称之为盈数。

由于 是最小的盈数，它的真约数之和为 ，所以最小的能够表示成两个盈数之和的数是 。通过数学分析可以得出，所有大于 的数都可以被写成两个盈数的和。

求所有不能被写成两个盈数之和的正整数之和。

思路

跟欧拉21 很相似
根据欧拉筛每个合数都被自身最小素因子筛到的特性
结合利用因子和公式，可以在线性时间内求出所有数的因子和

代码

// 素数筛算法求解因子和问题
#include <cstdio>

const int N = 28123;
int prime[N + 5];
int f[N + 5];
int cnt[N + 5]; // cnt[i] 记录 i 最小素因子的幂次
bool mark[N + 5];

void init() {
    for (int i = 2; i <= N; i++) {
        if (!cnt[i]) { // 如果是合数，则 cnt[i] 已经被标记过
            prime[++prime[0]] = i;
            f[i] = i + 1;
            cnt[i] = i;
        }
        for (int j = 1; j <= prime[0] && prime[j] * i <= N; j++) {
            if (i % prime[j]) {  // i 与 prime[j] 互素
                cnt[i * prime[j]] = prime[j];  // prime[j] 为 i * prime[j] 的最小素因子
                f[i * prime[j]] = f[i] * f[prime[j]];
            }
            else {
                cnt[i * prime[j]] = cnt[i] * prime[j];
                f[i * prime[j]] = f[i] * (cnt[i * prime[j]] * prime[j] - 1)
                                  / (cnt[i * prime[j]] - 1);  // 等比数列求和公式
                break;
            }
        }
    }
}

int main() {
    init();
    int k = 0;
    for (int i = 2; i <= N; i++) {
        if (f[i] > (i << 1)) f[k++] = i;
    }
    
    for (int i = 0; i < k; i++) {
        for (int j = i; j < k; j++) {
            if (f[i] + f[j] > N) break;
            mark[f[i] + f[j]] = true;
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        if (!mark[i]) ans += i;
    }
    printf("%d\n", ans);
    return 0;
}