素数筛法是个固定的模板，大部分情况只需要把模板一贴就可以了。出场率也很高，跟素数有关的题目基本上都需要。
判断一个数是否是素数()
这种情况，由于n比较小，按照素数的定义判断即可，即“只有1和它自己两个因子的，称为素数”
时间复杂度为
for (int i = 2;i * i <= n;i++) {
if (i % prime[j] == 0) {
return false;
}
}判断一个数是否是素数()
这个很超纲，笔试中几乎不会出现，有兴趣的同学可以自行百度一下米勒罗宾素数检测
时间复杂度为
筛选一段区间内的素数（朴素素数检测）
这种筛选方法根据素数的定义一个一个判断，容易想到的，虽然效率慢了点
时间复杂度为，可用数据范围是()
vector<int> prime;
prime.push_back(2);
for (int i = 3;i < N;i+=2) {
bool flag = true;
for (int j = 0;prime[j] * prime[j] <= i;j++) {
if (i % prime[j] == 0) {
flag = false;
break;
}
}
if (flag) {
prime.push_back(i);
}
}筛选一段区间内的素数（埃式筛法）
这种筛选方式对于每个素数，把这个素数的所有倍数全部标记成非素数
时间复杂度为，可用数据范围是()
素数筛法的时间复杂度计算问题，引申自一个计算公式：
bool isprime[N];
memset(isprime, true, sizeof(isprime));
for (int i = 2;i < N;i++) {
if (!isprime[i]) {
continue;
}
for (int j = i * 2;j < N;j+=i) {
isprime[j] = false;
}
}筛选一段区间内的素数（欧拉筛法）
埃式算法中，同一个合数会被筛几次，有几个素因子就被筛几次。欧拉筛法每个合数只被它最小的素因子筛一次，从而达到线性复杂度
时间复杂度为，可用数据范围是()
算法过程：扫描每个数x，我们遍历所有不大于x最小的素因子的素数p，将x*p标记成合数
bool isprime[N];
vector<int> prime;
memset(isprime, true, sizeof(isprime));
for (int i = 2;i < N;i++) {
if (isprime[i]) {
prime.push_back(i);
}
for (int j = 0;j < prime.size() && prime[j] * i < N;j++) {
isprime[prime[j] * i] = false;
if (i % prime[j] == 0) {
break;
}
}
}运用
题目来源：今年某次笔试题
我们知道每一个大于 1 的整数都一定是质数的乘积来表示，如 10=2*5。现在请设计一个程序，对于给定的一个(1, N]之间的正整数（N取值不超过10万），你需要统计(1,N]之间所有整数的因数分解后，所有质数个数的总个数。举例，输入数据为6，那么满足(1,6]的整数位2,3,4,5,6,，各自进行质数分解后为：2=>2，3=>3，4=>2*2，5=>5，6=>2*3。对应的质数个数即为1，1，2，1，2。最后统计总数为7
数据范围：n不超过10万
解析：
问题相当于 分解后有多少个素因子
方法一：
素数筛法，枚举所有的素数，分别统计 分解后有多少个素数 p，复杂度是
方法二：
素数筛法，素数筛选中，可以顺便把素数的个数求出来，复杂度是
int num[N];
int ret = 0;
for (int i = 1;i < N;i++) {
num[i] = i;
}
for (int i = 2;i < N;i++) {
if (num[i] == 1) {
continue;
}
for (int j = i;j < N;j += i) {
while (nums[j] % i == 0) {
ret++;
nums[j] /= i;
}
}
}方法三：
朴素素数检测，加迭代，复杂度是 ，对于 的数据量，能否过，有点悬
vector<int> prime;
int num[N] = {0,0,1};
prime.push_back(2);
for (int i = 3;i < N;i+=2) {
bool flag = true;
for (int j = 0;prime[j] * prime[j] <= i;j++) {
if (i % prime[j] == 0) {
flag = false;
num[i] = num[i / prime[j]] + 1;
break;
}
}
if (flag) {
num[i] = 1;
prime.push_back(i);
}
}