文章目录
前言
主要知识点
埃氏筛
扩展知识点
线性筛（欧拉筛）
课后习题详解
回文素数
思路
结果分析
前言
今天竟然有两讲，那我就要分两篇文章了，嘿嘿嘿。
主要知识点
埃氏筛
bool f[n]; f[0] = false; f[1] = false; memset(f , 1, n); for(int i = 2;i < n;i++){ if(f[i]){ for(long long j = (long long)i*i;j < n;j += i) f[j] = false; } }
其实就是如果找到一个素数，则这个素数所有的倍数都是合数。从i*i开始是因为i*i之前的已经被之前的元素筛了一边，避免重复。
扩展知识点
线性筛（欧拉筛）
其实上面的代码还是有缺点，比如3*10=30,5*6 = 10。会造成重复筛选，所以欧拉筛就是基于这种去处重复的思想。让每个合数只被最小质因子筛选一次。
bool f[n]; int x[n]; f[0] = false; f[1] = false; memset(f , 1, n); x[0] = 0; for(int i = 2;i < n;i++){ if(f[i]){ x[++x[0]] = i; } for(int j = 1;j <= x[0] && i*x[j] < n;++j){ f[i* x[j]] = false; if(i % x[j] == 0) break; } }
其中f[n]记录所有搜索到的素数，然后利用素数乘现在搜索到的元素乘来对i*i范围内元素进行筛选，这样不会造乘int类型的溢出。
课后习题详解
回文素数
204. 计数质数
https://leetcode-cn.com/problems/count-primes/
统计所有小于非负整数 n 的质数的数量。
思路
其实就是直接利用埃氏筛进行，标记为素数的时候做count就好了。
int countPrimes(int n){ if(n == 0|| n == 1) return 0; bool f[n]; f[0] = false; f[1] = false; memset(f , 1, n); int cnt =0; for(int i = 2;i < n;i++){ if(f[i]){ ++cnt; for(long long j = (long long)i*i;j < n;j += i) f[j] = false; } } return cnt; }
结果分析
还算可以把，也不算太拉跨，尝试了欧拉筛结果时间和空间复杂度都有一定规模的上升，感觉没啥必要。欢迎大佬尝试，给个参考。
int countPrimes(int n){ if(n == 0|| n == 1) return 0; bool f[n]; int x[n]; f[0] = false; f[1] = false; memset(f , 1, n); x[0] = 0; int cnt =0; for(int i = 2;i < n;i++){ if(f[i]){ x[++x[0]] = i; ++cnt; } for(int j = 1;j <= x[0] && i*x[j] < n;++j){ f[i* x[j]] = false; if(i % x[j] == 0) break; } } return cnt; }
这样引入一个int数组，一个int4字节直接大了好多。然后访问int类型几次之后也会更快到达buffer的末端引起缺页，所以可能性能更差吧。
