素数的定义
素数也叫质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是质数也不是合数）。
一、试除法（判断素数）
试除法顾名思义就是用 2 到 n?-?1 的数一个一个试除，如果 n 不能整除这之间所有的数，那么说明它就是素数。这样从 2 试到 n - 1，显然时间复杂度是的，那么有没有方法可以降低时间复杂度呢？答案是肯定有的，可以证明这个循环范围可以缩小到从 2 到?
，那么时间复杂度就缩短到了
。
再对循环式子进行稍微的变形，C++代码如下：
bool is_prime(int n)
{
if(n < 2) return false;
for(int i = 2; i <= n / i; i++) // 这里用 i <= n / i 或 i * i <= n 比 i <= sqrt(n)要好
if(n % i == 0)
return false;
return true;
}二、埃氏筛法（求一个范围中的所有素数）
试除法的弊端非常明显，如果要求一个范围中的所有素数，用试除法一个一个判断效率就太低了。
埃氏筛法是用于解决这类问题的古老而简单高效的方法，可以快速找到[2, n]中的所有素数。
具体操作是这样的：从2开始寻找素数，每次找到一个素数后就将它的倍数全部筛掉，并将该素数存储到另一个队列（数组）中，不断循环，直至原队列（数组）为空。
时间复杂度为。
C++代码如下：
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void E_sieve(int n){
for(int i = 2; i <= n / i; i++){
if(!st[i]){
primes[cnt++] = i;
for(int j = 2 * i; j <= n; j += i) // 这里可以优化成 int j = i * i
st[j] = true;
}
}
}三、欧拉筛法（埃氏筛法的优化版）
埃氏筛法中，由于一个数可以既是一个素数的倍数，又是另一个素数的倍数，可以发现这会出现重复标记的情况，即同一个数被筛掉了不止一次，浪费操作了。
欧拉筛法就是在埃氏算法的基础上多了判断的步骤，从而消去了这种重复标记的情况，核心思路是用合数中的一个因数筛掉这个合数。
具体操作为：利用已经求得的素数，第一重循环将区间内的数从小到大遍历，第二重循环将已求得的素数从小到大遍历，将这个数和素数的乘积标记为合数。如果一个数能被素数整除，跳出循环。
时间复杂度为。
C++代码如下：
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void Euler_seive(int n){
for(int i = 2; i <= n; i++){
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] <= n / i; j++){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break; // 如果这个数能被素数整除，跳出循环
}
}
}