找素数的三种方法：试除法、埃式筛法、线性筛

一、素数的定义

素数又被称为质数，就是大于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为例：

23456789101112131415161718192021222324252627282930

先用第一个素数2来排查表中的合数，2的整数倍有：

4 6 8 10 12 14 16 18 20 22 24 26 28 30

23456789101112131415161718192021222324252627282930

接下来是3的整数倍排查：

6 9 12 15 18 21 24 27 30

234567891011121314151617181920212223242526272829304不是素数，已经被排查了所以下一个为5的整数倍排查：

10 15 20 25 30 25 30

23456789101112131415161718192021222324252627282930三个回合已经将表中的合数清理完毕，剩下的就是素数了，思路展示完毕接下来是代码实现

vector 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 isPrime(n+1,true);//初始化，将所有数都看成素数

vector Prime;//用来存储素数的数组

for(int i=2;i<=n;i++)

{

if(isPrime[i]==true)//如果是素数就存入Prime数组

Prime.push_back(i);

for(int j=0;j

{

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

#include

using namespace std;

int n,count=0;

vector 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<

}

线性筛：

#include

#include

using namespace std;

vector isPrime(1e8+10,true);

vector 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

{

isPrime[i*Prime[j]]=false;

if(i%Prime[j]==0)

break;

}

}

for(int i=2;i<=n;i++)

if(isPrime[i])

count++;

cout<

}

最后在判断素数的时候区间要从2开始写，因为1不是素数也不是合数，但是在初始化的时候把1也看成素数了。