框架思维：将素数筛算法写成框架算法

任务

求 1 万以内所有素数的和。

编码

素数筛算法介绍

所谓素数筛，是将其产出的信息存储在一个标记数组中，数组的第 i 位，标记的是 i 这个数字是否是合数的信息。如果 i 这个数字是合数，数组下标为 i 的位置就被标记成为 1，如果 i 不是合数，则数组下标为 i 的位置就是 0。素数筛就是通过一套算法流程，产生一个这样的数组。

算法流程：

素数筛代码框架

int prime[10005] = {0};
void init_prime() {
    // 素数筛的标记过程
    for (int i = 2; i * i <= 10000; i++) {  //从 2 开始遍历到根号 10000，也就是 100。
        //i <= sqrt(10000) == i * i <= 10000
        //这种改变是有好处的，会在代码运行速度上做提升，毕竟开方运算是很慢的，远远没有单独做一个乘法操作要快。
        if (prime[i]) continue;  //判断 i 这个数字是否被标记过的，如果被标记过，就说明是合数，就不执行后续操作。
        // 用 j 枚举所有素数 i 的倍数
        for (int j = 2 * i; j <= 10000; j += i) {
            prime[j] = 1; // 将 j 标记为合数
        }
    }
    return ;
}

实现

#include <stdio.h>
#define MAX_N 10000
int prime[MAX_N + 5];

// 初始化素数表
void init_prime() {
     prime[0] = prime[1] = 1;
     for (int i = 2; i * i <= MAX_N; i++) {
         if (prime[i]) continue;
         for (int j = 2 * i; j <= MAX_N; j += i) {
             prime[j] = 1; // 将 j 标记为合数
         }
     }
     return ;
}

int main() {
    init_prime();
    int sum = 0;
    for (int i = 2; i <= MAX_N; i++) {
        sum += i * (1 - prime[i]); // 素数累加
    }
    printf("%d\n", sum);
    return 0;
}

//输出：5736396

思考题

1，因子分解程序正确性证明

所谓的素因子分解，就是把一个整数，表示成为若干个素数相乘的形式，并且我们可以轻松的证明，这种只由素数表示的分解表示法，对于某个特定整数 N 来说，一定是唯一的。
例如，67689 这个数字就可以分解为：3 * 3 * 3 * 23 * 109 = 67689，其中 3、23、109 都是素数。

下面呢，有一段素因子分解的程序：

#include <stdio.h>

// 打印一个素因子，并且在中间输出 * 乘号
void print_num(int num, int *flag) {
    if (*flag == 1) printf(" * ");
    printf("%d", num);
    *flag = 1;
    return ;
}

int main() {
    int n, i = 2, flag = 0, raw_n;
    scanf("%d", &n);
    raw_n = n;
    // 循环终止条件，循环到 n 的平方根结束
    while (i * i <= n) {
        //①：只要 n 可以被 i 整除，就认为 i 是 n 的一个素因子
        while (n % i == 0) {
            print_num(i, &flag);
            n /= i;
        }
        i += 1;
    }
    //②：如果最后 n 不等于 1，就说明 n 是最后一个素数
    if (n != 1) print_num(n, &flag);
    printf(" = %d\n", raw_n);
    return 0;
}

试证明：

1，第 18 行代码中，只要 n 可以被 i 整除，i 就一定是素数，为什么？
假设 i 可以被 n 整除，但 i 不是素数，由算术基本定理可知，一个非素数的数字 N，一定可以分解为几个小于 N 的素数乘积的形式。我们不妨假设 i=p1×p2，这里 p1 和 p2 均为素数，如果变量 n 可以被 i 整除，那么 n 也一定可以被小于 i 的素数 p1 整除。而根据程序的运行流程，n 中已经不可能存在小于 i 的因子了，所以 p1 不具备存在的条件，故原假设不成立，i 是素数。
2，第 25 行代码中，为什么只要 n 不等于 1，n 就一定是素数呢？
在 while 循环处理过程中，数字 n 中已经不可能存在小于等于 i 的所有的因子了，又因为此时 i 是大于根号 n 的一个值，也就是说，在小于等于根号 n 范围内，找不到数字 n 的非 1 因子，而能够满足这种性质的数字，一定是素数。

小结

想把具体“算法”升华成“算法思维”，首先要习惯性地总结算法的“框架思维”。
素数筛是用素数去标记掉这个素数所有的倍数。
清楚地知道素数筛在执行过程中，每一行的性质。