15 | 框架思维（下）：用筛法求解其他积性函数

胡光

你好，我是胡光，咱们又见面了。
上一节，我们讲了素数筛这个算法，并且强调了，要按照框架思维去学习算法代码，因为当你学会这么做的时候，它就可以变成解决多个问题的利器了。
本节我将带你具体使用素数筛算法框架，去解决一些其他简单的数论问题。通过解决这几个具体问题的过程，我希望你能找到“框架思维”的感觉。
今日任务今天这个任务，需要你依靠自己的力量来完成。不过你也不用担心，我会把需要做的准备工作都讲给你。
这个任务和因数和有关，什么叫做因数和呢？就是一个数字所有因数的和。那么什么是一个数字的因数呢？因数就是小于等于这个数字中，能整除当前数字的数。例如，28 这个数字的因数有 1、2、4、7、14、28 ，因数和就是各因数相加，即 56。
所以今天我们要做的，就是求出 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;
}
我们具体来看一下上面这个方法是怎么做的：在代码中，init_sum 函数内部就是初始化 sum 数组信息的方法，sum[i] 存储的就是 i 这个数字所有的因数和。在 init_sum 方法内部，使用了双重循环来进行初始化，外层循环 i 遍历 1 到 10000 所有的数字，内层循环遍历 1 到 i 所有的数字，然后找出其中是数字 i 因数的数字，累加到 sum[i] 里面，以此来计算得到数字 i 所有的因数和。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文介绍了如何利用框架思维和素数筛算法解决数论问题。首先，作者提出了一个任务：求解10000以内所有数字的因数和，并展示了一个简单但效率低下的解决方法。接着，文章分为三部分介绍了必备的数论基础知识，包括数论积性函数的定义和性质，以及如何利用递推公式来提高计算效率。通过这些知识，读者可以理解如何利用框架思维和素数筛算法来解决复杂的数论问题。文章还提供了相关代码示例，展示了如何利用素数筛框架和数论积性函数来快速计算因数数量。最后，读者被鼓励参照文章内容完成求解“因数和”的任务，并强调了“框架思维”在实际工作中的重要性。整体而言，本文以简洁清晰的语言，引导读者了解了如何运用框架思维和算法解决数论问题，为读者提供了一种新的解决问题的思路。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《人人都能学会的编程入门课》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(16)

最新
精选

1043
数学不太好，这节课听着有点一脸懵那啥……在隔壁黄申老师那里听说程序员不用把所有数学都学一遍，他会讲程序员只要用到的就会讲到，现在刚开始听还没建立起来框架……《得到》app的吴军老师说程序员除了要熟练掌握数学归纳法和逻辑思维的严谨性之外还得掌握离散数学。胡老师给准备的框架算法思维这个照猫画虎听着是感觉更有效率、更棒，但是数学不太好、大学阶段的数学全还回去，高中的剩的也不多，听今天的课确实有点懵，真没必要再好好学学高等数学啥的吗？
作者回复: 根据岗位不一样，对于数学的要求也不同。大多数岗位，确实用不着高等数学。可是研发岗的话，还是需要多补充补充的。
2020-04-11

6
一日
这个示例代码是不是有点问题，prime[i]好像有可能为0，i * i < MAX_N的条件，假如MAX_N取值为20，那prime[5]就为0，在计算因子数量时，i为5时，程序会报错的吧。
作者回复: perfect！对的，循环条件这里会导致 prime 数组初始化不完全！你是第一个发现问题的！想一想，怎么改这个 Bug 呢？^_^
2020-03-02

1
奕
12 的因数需要满足什么条件呢？第一，就是 12 的所有因数中只能包含 2 和 3 两种素因子；第二，就是 12 的所有因数中，2 和 3 素因子的幂次，不能超过 12 本身的 2 和 3 素因子的幂次 --------------------------------------- 对于上面这句话没有理解。关于第一点，一个数的素因子不是确定的吗？还要规定只能包含某个素因子？第二点：什么叫做 “不能超过 12 本身的 2 和 3 素因子的幂次” ，没理解这句话
作者回复: 你把 12 的因子都写出来，然后用素数的形式表示一下，你看看 12 的因子，都有什么特点。我们之所以要观察 12 因子的特点，是因为后续，我们需要通过某种方法，反向构造出 12 的因子。关于第2点的解释，你想想8也含有素数2，12也含有素数2，为什么8不是12的因子？因为8里面，含有3个素数2，也就是2的三次方，12只含有2个2，所以如果一个数字是12的因子，那么这个数字中素因子 2 的幂次，肯定不超过 2 次。
2020-02-23
2
1
罗耀龙@坐忘
茶艺师学编程继续…… /*课文例子因数和*/ #include <stdio.h> #define MAX_N 10000 int prime[MAX_N + 5] = {0}; void init_prime(){ for (int i = 2; i * i <= MAX_N; i++){ if(prime[i])continue; prime[i] = i; for(int j = 2 * i; j <= MAX_N; j +=i){ if(prime[j])continue; prime[j] = i; } } for (int i = 2; i <= MAX_N; i++){ if (prime[i] == 0)prime[i] = i; } return ; } int gcnt[MAX_N + 5]; void init_gcnt(){ gcnt[1] = 1; for (int i = 2; i <= MAX_N; i++ ){ int n = i, p = prime[i]; while ( n % p == 0){ n /= p ; gcnt[i] = n + p; } gcnt[i] = gcnt[n] * gcnt[p]; } return ; } int main(){ init_prime(); init_gcnt(); int a = 0; for(int i = 1; i <= MAX_N; i++){ a += gcnt[i]; } printf("%d", a); return 0; } //结果为 50052146
作者回复: 这个结果是不对的。你可以打印前10个数字的因子和结果，检查一下。
2020-07-12


罗耀龙@坐忘
茶艺师学编程感觉折腾了这么久，得出的结果都是错的…… /*课文里的例子完整版*/ #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(); int a = 0; for(int i = 1; i <= 10000; i++){ a += sum[i]; } printf("%d", a); return 0; } //结果是82256014 /*课文例子因数数量*/ #include <stdio.h> #define MAX_N 10000 int prime[MAX_N + 5] = {0}; void init_prime(){ for (int i = 2; i * i <= MAX_N; i++){ if(prime[i])continue; prime[i] = i; for(int j = 2 * i; j <= MAX_N; j +=i){ if(prime[j])continue; prime[j] = i; } } for (int i = 2; i <= MAX_N; i++){ if (prime[i] == 0)prime[i] = i; } return ; } int g_cnt[MAX_N + 5]; void init_g_cnt(){ g_cnt[1] = 1; for (int i = 2; i <= MAX_N; i++ ){ int n = i, cnt = 0, p = prime[i]; while ( n % p == 0){ cnt += i; n /= p ; } g_cnt[i] = g_cnt[n] * (cnt +1); } return ; } int main(){ init_prime(); init_g_cnt(); int a = 0; for(int i = 1; i <= MAX_N; i ++){ a += g_cnt[i]; } printf("%d", a); return 0; } //结果为1946815124
作者回复: 首先，你得先推导出来因数和的公式，然后将因数和的公式，看看怎么和代码框架相结合，你现在的结合方式还有点儿不太对。
2020-07-12


杜
老师您好：能否把通过素数筛和数论积性函数计算10000 以内所有数字的因数和的完整代码发一下？
作者回复: 这样，你可以试着补全其余部分，要是实在过不去，把代码发上来，我帮你找错误。
2020-04-11


一日
示例代码问题修改：因为prime[i]的值为0时，是素数，那它的素因子就只有1和它本身吧，是不是加一个if条件判断，如果为0时，就是下标i的值
作者回复: 对的，在外层额外增加一个循环遍历过程即可，把所有0值位都改成i，d(^_^o)
2020-03-03


Jinlee
我又回来了，我又回来了，花了一天多的时间把框架思维的两节课复习了一下，上次没看懂的这次看懂了😬上网查了因数和的资料，然后按照老师求因数个数的方法把求因数和的代码实现了，我太激动了！😊体会到了一点递归的思想，这么晚来留言老师会看到吗😌代码如下 #include <stdio.h> #include <math.h> #define MAX_N 10000 /* 初始化数组prime,数组元素是下标i对应的最小素因子 */ int prime[MAX_N + 5]; void init_prime() { int i, j; for (i = 2; i * i <= MAX_N; i++) { if (prime[i]) continue; // 素数中最小的素因子是其本身 prime[i] = i; for (j = 2 * i; j <= MAX_N; j += i){ if (prime[j]) continue; // 如果 j 没有被标记过，就标记成 i prime[j] = i; } } return ; } /* 构造一个求等比数列和的函数 */ int sum_array(int num, int n) { int i, sum = 0; for (i = 0; i <= n; i++){ sum += pow(num, i); } return sum; } /* 利用prime数组和等比数列和函数初始化数组sum_divisor,数组元素是下标对应的约数和 */ int sum_divisor[MAX_N + 5]; void init_sum_divisor() { init_prime(); /* 1的约数和就是1 */ sum_divisor[1] = 1; int i; for (i = 2; i * i <= MAX_N; i++){ int n = i, cnt = 0, p = prime[i]; // 得到i中包含cnt个最小素因子p while (n % p == 0) { cnt += 1; n /= p; } // 此时的n和包含cnt个最小素因子p的部分是互素的 sum_divisor[i] = sum_divisor[n] * sum_array(p, cnt); // 上面一行代码其实是利用了递归的思想，边界条件就是sum_divisor[1]=1，注意体会 } return ; } int main() { init_sum_divisor(); int n; prntf("请输入你要计算的约数和对应的整数：") scanf("%d", &n); printf("%d的约数和是%d.", n, sum_divisor[n]); return 0; }
作者回复: 非常不错的！有个小问题： sum_divisor 初始化过程中的 i 变量范围设置错了，你只能初始化根号 MAX_N 范围以内的数字的因子和
2020-02-28
3

宋不肥
//嵌入欧拉筛版 #include <stdio.h> #include <math.h> #define MAX_N 100 int p[MAX_N + 1] = {0}; int p_sum[MAX_N+1] = {0} ; // 欧拉筛最小素因子 void Euler() { p[1] = 1; p_sum[1] = 1; for (int i = 2; i <= MAX_N; i++) { if(p[i] == 0){ p[i] = i; p_sum[i] = i+1; } for (int j = 2; j <= MAX_N; j++) { if(i * p[j] > MAX_N) break; p[i * p[j]] = i; if(i % p[j] != 0){ p_sum[i*p[j]] = p_sum[i]*p_sum[p[j]]; } if(i % p[j] == 0){ p[i]=p[j]; int cnt = 0, n = i; while (n % p[j] == 0) { cnt += 1; n /= p[j]; } int mid_sum = 0; for(int z=0;z <= cnt;z++){ mid_sum += pow(p[j],z); } p_sum[i] = p_sum[n] * mid_sum; p_sum[i*p[j]] = p_sum[n] * (mid_sum + pow(p[j],cnt+1) ); break; } } } return ; } int main() { Euler(); for(int i = 0;i <= MAX_N;i++){ printf("%d\t",p_sum[i]); } }
作者回复: 不错，不过p_sum[i]在i与p[j]不互素中的赋值操作是多余的。
2020-02-22


宋不肥
因数和： #include <stdio.h> #include <math.h> #define MAX_N 100 int p[MAX_N + 1] = {0}; int p_sum[MAX_N+1] = {0} ; // 欧拉筛最小素因子 void Euler() { for (int i = 2; i <= MAX_N; i++) { if(p[i] == 0) p[i] = i; for (int j = 2; j <= MAX_N; j++) { if(i * p[j] > MAX_N) break; p[i * p[j]] = i; if(i % p[j] == 0){ p[i]=p[j]; break; } } } return ; } void init_p_sum() { // 1 的因数和就是 1 p_sum[1] = 1; for (int i = 2; i <= MAX_N; i++) { int n = i, cnt = 0, mid_sum = 0, min = p[i]; // 得到数字 n 中，包含 cnt 个最小素因子 min while (n % min == 0) { cnt += 1; n /= min; } // 此时数字 n 和最小素数 min 部分，就是互素的 for(int j=0;j <= cnt;j++){ mid_sum += pow(min,j); } p_sum[i] = p_sum[n] * mid_sum; } return ; } int main() { Euler(); init_p_sum(); for(int i = 0;i <= MAX_N;i++){ printf("%d\t",p_sum[i]); } }
作者回复: 程序的思路没有错，其实可以把因数和的过程，直接镶嵌到欧拉筛的算法中，而不是像素数筛一样。欧拉筛可以做到，求完素数以后，因数和就求完了。你主要观察你代码欧拉筛中的标记过程，标记过程，使用 i 标记掉 i * p[j]，而此时 p[j] 是素数，而且明显有两种情况：1、p[j] 与 i 互素以及 p[j] 与 i 不互素。互素的情况用积性函数的性质，直接计算即可，不互素的情况，稍微处理一下即可。^_^
2020-02-22



收起评论