14 | 框架思维（上）：将素数筛算法写成框架算法
今日任务
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了素数筛算法的框架思维及其在算法思维中的重要性。文章首先阐述了素数的概念和素数筛算法的思想和流程，通过示例代码演示了如何使用素数筛算法找出指定范围内的素数。文章强调了素数筛算法的正确性，并通过数学归纳法的证明展示了其有效性。此外，文章还提供了关于素因子分解程序正确性证明的思考题，以及使用素数筛算法求解1万以内所有素数的和的示例代码。最后，文章总结了素数筛算法的框架思维，强调了理解算法代码的重要性，并鼓励读者熟记素数筛的算法框架。整体而言，本文内容简洁清晰，适合读者快速了解框架思维和素数筛算法的基本原理。文章内容涵盖了算法思维的重要概念，对于算法学习者具有一定的指导意义。
《人人都能学会的编程入门课》，新⼈⾸单¥59
全部留言(18)
- 最新
- 精选
🤪HappyJoo老师请问一下，您觉得有必要把这几个在文中出现的代码“背”下来吗？因为在看代码的时候总觉得好像会写，但是实际上去写不看您的代码的时候，就写不出来了。身为一个合格的程序员，应该要有能力，可以脱离您的教程，独自根据题目要求，写出代码吧？作者回复: 你可以把代码的学习看成两部分，第一部分是熟练程度，第二部分是逻辑性，其中想要提升熟练程度，只有多敲多打，我现在还没有找到太好的办法，让人不写一行代码，就学会编程。-_-|||
2020-02-165- 🤪HappyJoo1，for (int i = 2; i <= MAX_N; i++) { sum += i * (1 - prime[i]); } 2，for (int i = 2; i <= MAX_N; i++) { if (!prime[n]) sum += i; } 老师你好，突然想问一下，这里哪个效率更高呢？我猜是第二个嘿嘿嘿~
作者回复: 这个要是单纯来说的话，我认为，应该是第二个效率高一些。因为第二个使用了 if 分之条件，就会触发 CPU 的分之预测动作，只要有预测成功的情况，对于执行效率来说的话就是正向收益。
2020-03-063 
信念i * i <= MAX_N 这个判断条件真是学到了作者回复: d(^_^o)
2020-06-012
罗耀龙@坐忘
茶艺师学编程 1、思考题 （1）反证一下，如果n可以被整除，但i就是合数--这样的情况完全有可能。然而合数是素数的倍数，就是说被选到的这个i是对应的素因子后面，问题是程序是从前往后一个一个地检验过来的，那么这个i怎么就直接跳到后面呢？所以这里就矛盾了。 因此按照程序规定的从前往后，只要n可以被i整除，i就一定是素数。 （2）我做不出来…… 2、课文提到的欧拉筛替换挑战 我也是参考别人的…… // 欧拉筛素数（带视窗的） void Euler() { for (int i = 2; i <= MAX_N; i++) { if(p[i] == 0) p[PrimeNum++] = i;//这里把p数组按顺序（2-10000）“刷”上数字 for (int j = 2; j <= MAX_N; j++) { if(i * p[j] > MAX_N)// 在用i刷数字的时候，用数组p来框定范围：i*p[j]<10000 break; p[i * p[j]] = 1;//在上用 i * p[j]来圈定就算范围，在这里当做P数组的指针来标记合数（指针为合数的话对应的数组值为1） if(i % p[j] == 0)//如果i能被p[j]整除（倍数），那这个数就跳过 break; } } return ; } int main() { Euler(); int sum = 0; for (int i = 0; i <= PrimeNum; i++) { printf("%d\n", p[i]); sum += p[i]; } printf("\n一万以内的素数和：%d\n", sum); return 0; } 这里有个疑问，我这里看到的欧拉筛出来的就是素数，那么合数标记p[i * p[j]] = 1怎么就不见呢？是因为下面的break直接让“1”消失了吗？作者回复: 能有这样的思考很不错。d(^_^o) 关于你的疑问，要理解一点，合数 N = p * M，其中 p 是 N 中最小的素数，也就是程序中的 p[j]，M 就是程序中的 i。如果不 break，继续向后枚举 N=i * p[j] 的话， p[j]就不是 N 中最小的素因子了。
2020-06-281
宋不肥欧拉法： #include <stdio.h> #define MAX_N 10000 int PrimeNum=2; int p[MAX_N + 1] = {0}; // 欧拉筛素数 void Euler() { for (int i = 2; i <= MAX_N; i++) { if(p[i] == 0) p[PrimeNum++] = i; for (int j = 2; j <= MAX_N; j++) { if(i * p[j] > MAX_N) break; p[i * p[j]] = 1; if(i % p[j] == 0) break; } } return ; } int main() { Euler(); int sum = 0; for (int i = 0; i <= PrimeNum; i++) { sum += p[i]; } printf("%d\n", sum); return 0; }作者回复: 可以的！d(^_^o)，再试着把因子个数公式加到这个框架中。就更好了！
2020-02-201
宋jia wen老师 void print_num(int num , int *flag) 为什么加“*”，直接写flag 不行吗作者回复: 不行，输出的过程中需要有一个类似全局变量的东西记录是否输出过，这个值需要记录在flag变量中，如果没有*，就起不到记录的效果。
2020-02-181
奕在声明素数筛 prime 数组的大小时为什么要加上5呢？这个5是怎么得到的？作者回复: 哦哦哦，只是空间稍微开大一点点。个人编码习惯。
2020-02-151
乘坐Tornado的线程魔法师内容干货慢慢，理解思想最重要。 P.S. 小编，你看如果这样设定标题捏? "将素数筛选算法写成框架算法""作者回复: d(^_^o)
2020-02-1521
Noya#include <iostream> using namespace std; const int N = 1e6 + 10; int n; int st[N]; void init_prime(int n) { for (int i = 2; i <= n; i++) { if (st[i]) continue; for (int j = i * 2; j <= n; j += i) { if (!st[j]) st[j] = 1; } } return; } int main(void) { scanf("%d", &n); init_prime(n); for (int i = 2; i <= n; i++) { if (!st[i]) { if (i > 2) printf(" "); printf("%d", i); } } return 0; }作者回复: d(^_^o)
2020-05-20
小风老师，那个flag初始为0，中间也没看到有变化啊，为什么判定条件*flag＝＝1成立呢？作者回复: 注意观察代码的第7行，flag 的值是有变化的。
2020-05-07
