素数又名不可约数，设 $p \ne 0,\pm 1,(p \in Z)$，若 $p$ 除了 $\pm 1$ 和 $\pm p$ 以外没有其他约数，则 $p$ 为素数。平时提到素数默认是正整数。
[!tip] 以下算法中会有很多优化的部分是根据数学定理进行的，想要深究需要去理解数论的内容。
定理1#
除1以外，每一个正整数都是素数的乘积。（证明略）
这是数论的基础，一些经典数论书开篇就会提到。每一个算法都有其数学公式或者定理的原型，我们不过是用代码将其写一遍。
应用#
求 $\pi(n)$ ，即求n以内有多少个素数
朴素算法（试除法）#
根据素数的定义，除了1和他自身，没有其他约数，用 $[2,p-1]$ 中的每一个数与这个数相除来验证
bool isprime(int p)
{
if (p<=1) return false;
for (int i=2;i<p;i++) //[2,p-1]中的所有数
if (p%i==0) return false;
return true;
}
void solve(int n)
{
for (int i=1;i<=n;i++)
if (isprime(i)) cout<<i<<" ";
}
埃氏筛#
根据[[#定理1|定理1]]，我们可以用素数的倍数找到n以内的所有合数，去掉后便是素数。
该算法复杂度为：$\displaystyle O(n\log\log n)$
void fun(int n)
{
vector<bool> isprime(n + 1,true);
for (int i=2;i*i<=n;i++)//i*i：只用筛选到平方根
{
if (isprime[i]) //只求素数的倍数
{
if (i*i>n) continue;
for (int j=i*i;j<=n;j+=i) //i*i的原因：i-1的倍数已经筛选过，去除重复
isprime[j]=false;
}
}
for (int i=2;i<=n;++i)
if (isprime[i]) cout<<i<<" ";
}
欧拉筛(线性筛)#
欧拉筛多了关键一步的剪枝，去除重复的标记。它的核心概念是让合数被最小的素约数进行标记，保证 i*j，其中 j 为最小的素约数
该算法复杂度为：$\displaystyle O(n)$，对埃氏筛的再优化
void fun(int n)
{
vector<bool> isprime(n + 1,true);
vector<int> primes;
for (int i=2;i<=n;i++)
{
if (isprime[i]) primes.push_back(i); //存储素数
for (int j:primes) //遍历素数数组
{
if (i*j>n) break; //n以后的不标记
isprime[i*j]=false;//标记j这个素数的所有倍数i
if (i%j==0) break;//当i能被j整除，即j已经是i的一个约数。
//这意味这j是i的最小素约数（即i已有更小的素约数）
//如果我们用更大的素数j'乘上i，就不满足用最小素数的倍数求合数
}
}
for (int i:primes)
cout<<i<<" ";
}
其他应用#
欧拉筛的副产物就是每个数的最小素约数，将 vector<bool> isprime 改为 vector<int> mi nprime; 来储存即可。
/*
代码中只有三处需要改动（注释部分）
*/
void fun(int n)
{
vector<int> minprimes(n+1);//开足n的空间
vector<int> primes;
for (int i=2;i<=n;i++)
{
if (minprimes[i]==0)
{
primes.push_back(i);
minprimes[i]=i; //储存的不是bool值，而是当前的素数
}
for (int j:primes)
{
if (i*j>n) break;
minprimes[i*j]=j; // 储存的不是bool值，而是当前的素数
if (i%j==0) break;
}
}
for (int i:minprimes)
cout<<i<<" ";
}