目录
前言
前些天写了一个查找范围区间的素数个数的题目，有两组数据一直tle，所以就特此学习了一些素数算法，所以又写了一遍，一是为了让自己对代码的熟悉程度有提高，一方面也是积累自己的算法模板。
一.遍历查找
对于素数的算法，最简单的就是遍历，但他只限于小范围，范围一大就会tle或者栈溢出，对于小范围的使用是最直接，最好理解的。由一下问题为例：
/*问题：输出范围为1到1e2内所有的素数的个数*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2;
static int is_primes(int a)
{
int flag = 1;
for (int i = 2;i <= sqrt(a);i++)
{
if (a % i == 0)
{
flag = 0;
break;
}
}
return flag;
}
int main()
{
int count = 0;
double s = clock();
for (int i = 2;i <= N;i++)
{
int flag = is_primes(i);
if (flag)
{
count++;
}
}
double c = clock();
printf("%d\ntime=%.0lfms", count, c - s);
return 0;
}
结果：
可以看到，如果范围比较小的时候，普通的遍历还是比较可以的，至少能做到在0ms以内,但我们只要稍微把范围扩大，例如从1到1e5，这时，输出时间大大增加，直接看数据觉得还好，但是和接下来讲的两种算法简直就是降维打击
这是输出结果：
二.埃氏筛法
核心思想:埃氏筛的核心思路就是利用合数和素数的关系来排除大量数据，例如合数4，4可以拆成2*2，也就是两个素数的乘，所以合数可以拆成2个或多个素数的乘积，我们可以利用这一点进行筛除。我们举一个例子：
例如，求2-10之间的素数。我们先确定2是素数，所以2的倍数（除2以外）就一定不是素数，所以我们把4，6，8，10划去；接下来下一个没被划去的数为3，发现3是素数，所以划去6，9；再接下来就是4，但已经被划去了，所以是5，所以把10划去，接下来没有新的未划去的数，所以剩下的2，3，5，7就是这个范围内所有的素数了。
知道了核心思路，我们该如何将代码真正实现呢？首先我们得知道哪些数是被我们排除的，所以我们可以利用标记数组，对素数和合数进行标记，令素数为0，合数为1，类似于哈希表的思想。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int is_primes(int a)
{
int flag = 1;
for (int i = 2;i <= sqrt(a);i++)
{
if (a % i == 0)
{
flag = 0;
break;
}
}
return flag;
}
int pri[N+10];//素数 0；合数 1
int main()
{
int count = 0;
double s = clock();
for (int i = 2;i <= sqrt(N);i++)
{
if (is_primes(i))
{
for (int j = 2 * i;j <= N;j += i)
{
pri[j] = 1;
}
}
}
for (int i = 2;i <= N;i++)
if(!pri[i]) count++;
double c = clock();
printf("%d\ntime=%.lfms", count, c - s);
return 0;
}输出结果：
可以明显看到，速度快了不少，那我们再把数据扩大至1e7呢？结果会是多少？
其实这个代码还可以继续优化，将判断素数的范围再改一下，将sqrt（a）改成i<=a/i。我们再来看看时间会是多少？
时间基本控制在109ms范围，又快了一点点，那这是不是素数筛的完全形态呢？
当然不是，在之前的例子中，相信大家已经能感觉到，我们在筛数时有些数是被重复筛了的，例如6，10，都被2和5这两个素数筛了一遍，这样就形成了大量无用时间的开销，所以算法还可以优化。也就是下面要讲到的欧拉筛。但是在讲欧拉筛之前，我们再看看之前的代码
在这里面，if语句里真的还要判断是否为素数呢？假设i=7，说明i到7之前所有的素数都没有把7筛除，是不是就可以说明7就是素数了，并不需要再进入函数判断7是否为素数了。
所以，埃氏筛最后优化出来的代码应该是这样的：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7;
int pri[N+10];//素数 0；合数 1
int main()
{
int count = 0;
double s = clock();
for (int i = 2;i <= N/i;i++)
{
if (!pri[i])
{
for (int j = 2 * i;j <= N;j += i)
{
pri[j] = 1;
}
}
}
for (int i = 2;i <= N;i++)
if(!pri[i]) count++;
double c = clock();
printf("%d\ntime=%.lfms", count, c - s);
return 0;
}
三.欧拉筛法（终极版）
欧拉筛就是在埃氏筛的基础上进行优化，保证每个数只被筛掉一次，大大减少代码运行时间。我们引用一个数组存放判断出来的素数，在循环中，对i和这个数组的所有元素判断，看是否可以整除，从而是否跳出循环，来保证每个数只被筛一遍。
代码奉上：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7;
int pri[N+10];//素数 0；合数 1
int primes[N + 10], p = 0;
int main()
{
int count = 0;
double s = clock();
for (int i = 2;i <= N;i++)
{
if (!pri[i])
{
primes[++p] = i;
count++;
}
for (int j = 1;primes[j]*i<=N && j <= p;j++) //查找是否已经被筛过，如果之前的素数就已经筛过，就break
{
pri[primes[j] * i] = 1;
if (i % primes[j] == 0) break;
}
}
/*for (int i = 2;i <= N;i++)
if(!pri[i]) count++;*/
double c = clock();
printf("%d\ntime=%.0lfms", count, c - s);
return 0;
}
同样是1e7的范围，我们来看看欧拉筛每次需要的时间是多少？
是不是有种被降维打击的感觉，相比较于埃氏筛的代码，运行时间差不多减少了一半！足以看出欧拉筛的强大（强大无需多言）
结语
学会了这两种素数筛之后，相信你对素数的判断和统计已经不再害怕，甚至做到游刃有余，那我们离题目AC还会远吗？
标签：10,埃氏,筛法,int,合数,素数,线性,欧拉 From： https://blog.csdn.net/2403_88817808/article/details/144936618