找素数的三种方法：试除法、埃式筛法、线性筛
找素数的三种方法：试除法、埃式筛法、线性筛
素数（质数）是数论中的重要概念，寻找素数的方法也是算法学习中的经典问题。本文将介绍三种常见的素数寻找方法：试除法、埃式筛法和线性筛法，并通过洛谷的一道基础题目展示算法的实际应用。
一、素数的定义
素数又被称为质数，就是大于1的自然数中，除了1和它本身以外不在有其他因数，反之则为合数。
注：0和1既不是素数也不是合数。
二、判断素数的方法
1.试除法
对于一个整数n，对其从2~sqrt(n) 区间中判断，若不存在一个数i使得n%i==0，即可判断n为素数，反之n为合数。通过这个思路，我们即可写出代码。
bool isPrime(int n)
{
int i;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
return false;//如果找到除1和自身以外的因数，则为合数
}
return true;//找不到其他因数则为素数
}
为什么判断到sqrt(n)就行了呢？
因为当有一个大于sqrt(n)的因数就必然会有一个小于sqrt的因数出现，所以区间到sqrt(n)就行了。
2.埃式筛法
一般的，素数的整数倍一定是合数，用这个思想将合数一一排除，剩下的就是素数。
我们先以区间2~30为例：
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
先用第一个素数2来排查表中的合数，2的整数倍有：
4 6 8 10 12 14 16 18 20 22 24 26 28 30
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
接下来是3的整数倍排查：
6 9 12 15 18 21 24 27 30
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
4不是素数，已经被排查了所以下一个为5的整数倍排查：
10 15 20 25 30 25 30
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
三个回合已经将表中的合数清理完毕，剩下的就是素数了，思路展示完毕接下来是代码实现
vector<bool> isPrime(n+1,true);//初始化数组，先将所有数都看成素数在一个个排查
for(int i=2;i*i<=n;i++)
{
if(isPrime[i]==true)
{
for(int j=i*i;j<=n;j+=i)//遍历素数的整数倍
{
isPrime[j]=false;//将素数的整数倍标记
}
}
}
但我们很快就能发现这种算法的问题，例如10这个合数，在2的整数倍和5的整数倍中都出现了，也就是说重复排查，这也就导致了时间上的冗余，我们有什么办法来解决呢？
接下来要展示的线性筛完美的解决了这个问题。
3.线性筛
任何一个大于1的正整数n都可以拆解为多个质因数的乘积，任何一个合数都有它最小的质因数，通过这个最小质因数来做标记，即可解决重复排查的问题。
例如：12=2x2x3，有2和3这两个因数，所以用埃式筛法时会重复标记到。
因此我们需要定义一个新数组prime用来存放素数，因为素数是某个合数的因数，我们就用这个素数来乘出合数。
vector<bool> isPrime(n+1,true);//初始化，将所有数都看成素数
vector<int> Prime;//用来存储素数的数组
for(int i=2;i<=n;i++)
{
if(isPrime[i]==true)//如果是素数就存入Prime数组
Prime.push_back(i);
for(int j=0;j<Prime.size()&&i*Prime[j]<=n;j++)//将i区间的数乘上一个素数得到的定是合数
{
isPrime[i*Prime[j]]=false;
if(i%Prime[j]==0)//如果i%Prime[j]成立，说明 i*Prime[j+1]能被更小的素数所分解，所以跳出循环，不急着被Prime[j+1]分解。
break;//跳出循环，提高效率。
}
}
三.实操
找了洛谷上一道很基础的题，第一种方法就不展示了，主要是后面两种方法。
题目描述
求 1,2,⋯ ,𝑁1,2,⋯,N 中素数的个数。
输入格式
一行一个整数 𝑁N。
输出格式
一行一个整数，表示素数的个数。
输入输出样例
输入 #1复制
10
输出 #1复制
4
说明/提示
对于 40%40% 的数据，1≤𝑁≤1061≤N≤106。
对于 80%80% 的数据，1≤𝑁≤1071≤N≤107。
对于 100%100% 的数据，1≤𝑁≤1081≤N≤108。
题解
埃式筛法：
#include<iostream>
#include<vector>
using namespace std;
int n,count=0;
vector<bool> isPrime(1e8+1,true);
int main()
{
cin>>n;
for(int i=2;i*i<=n;i++)
{
if(isPrime[i])
{
for(int j=i*i;j<=n;j+=i)
{
isPrime[j]=false;
}
}
}
for(int i=2;i<=n;i++)
{
if(isPrime[i]==true)
count++;
}
cout<<count<<endl;
}
线性筛：
#include<iostream>
#include<vector>
using namespace std;
vector<bool> isPrime(1e8+10,true);
vector<int> Prime;
int n,count=0;
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
if(isPrime[i]==true)
Prime.push_back(i);
for(int j=0;j<Prime.size()&&i*Prime[j]<=n;j++)
{
isPrime[i*Prime[j]]=false;
if(i%Prime[j]==0)
break;
}
}
for(int i=2;i<=n;i++)
if(isPrime[i])
count++;
cout<<count<<endl;
}
最后在判断素数的时候区间要从2开始写，因为1不是素数也不是合数，但是在初始化的时候把1也看成素数了。