框架思维：用筛法求解其他积性函数

任务

求出 10000 以内所有数字的因数和。

可能已经想好的方法：

#include <stdio.h>
int sum[10005] = {0};

void init_sum() {
    // 循环遍历 1 到 10000 的所有数字
    for (int i = 1; i <= 10000; i++) {
        // 用 j 循环枚举数字 i 可能的因数
        for (int j = 1; j <= i; j++) {
            // 当 i%j 不等于 0 时，说明 j 不是 i 的因数
            if (i % j) continue;
            sum[i] += j;
        }
    }
    return ;
}

int main() {
    init_sum();
    printf("hello world\n");
    return 0;
}

效率较低，所以弃了。

编码

数论积性函数

所谓数论积性函数，首先，是作用在正整数范围的函数，也就是说函数 f(x) = y 中的 x 均是正整数。其次，是数论积性函数的一个最重要的性质，就是如果 n 和 m 互质，那么 f(n*m) = f(n) * f(m) 。

因数个数函数

因数个数：就不难理解了，它指的是一个数字因数的数量。例如，数字 6，有 1、2、3、6 这 4 个因数，因数个数就是 4。

素数筛框架


#define MAX_N 10000
int prime[MAX_N + 5] = {0};
void init_prime() {  //初始化 prime 数组信息
    for (int i = 2; i * i <= MAX_N; i++) {
        if (prime[i]) continue;  //prime[i] 中记录的是数字 i 中最小的素因子
        // 素数中最小的素因子是其本身
        prime[i] = i;  
        for (int j = 2 * i; j <= MAX_N; j += i) {
            if (prime[j]) continue;
            // 如果 j 没有被标记过，就标记成 i
            prime[j] = i;
        }
    }
    for (int i = 2; i <= MAX_N; i++) {
        if (prime[i] == 0) prime[i] = i;
    }
    return ;
}

实现

#define MAX_N 10000
int prime[MAX_N + 5] = {0};
int g_cnt[MAX_N + 5];
void init_g_cnt() {
    // 1 的因数数量就是 1 个
    g_cnt[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        int n = i, cnt = 0, p = prime[i];
        // 得到数字 n 中，包含 cnt 个最小素因子 p
        while (n % p == 0) {
            cnt += 1;
            n /= p;
        }
        // 此时数字 n 和最小素数 p 部分，就是互素的
        g_cnt[i] = g_cnt[n] * (cnt + 1);   
    }
    return ;
}

小结

所谓代码框架，就是要活学活用。
在真正的工作中，你所做的事情，大多是在多种代码框架之间做选择及组合拼装，每个算法代码只会解决遇到的一部分问题。而你在使用这些算法代码的时候，往往不能照搬照用，反而要做一些适应性的改变，这些都是“框架思维”中所重视的。