素数筛选法

素数,是指因子只包含1和其本身的数,那么,我们怎么大批量的判断素数呢?

(以下代码均基于打表(1~1e6)的基础上完成)

1.按照定义计算

素数的定义就是一个数的因子只包含1和其本身,那么我们直接就按照定义写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include<stdio.h>

# include<string.h>

# define maxn 1000000+10

int pri[maxn];
int isprime(int n)
{
for(int i=2;i<n;i++)
if(n%i==0)
return 0;
return 1;
}
int main()
{
pri[1]=0;
for(int i=2;i<=maxn;i++){
pri[i]=isprime(i);
}
return 0;
}

这是最基础的写法,也是最小白的写法。

这种算法的复杂度为O(n^2),复杂度非常的大,对于1e6的数据范围来说肯定要超时,那么还有没有更优化的算法?答案是肯定的

2.基于定义计算的优化算法

我们对一个合数进行考虑,例如12:

它的因子有1 2 3 4 6 12 ,而且1*12=12 , 2*6=12 , 3*4=12

可见,每一个因子都会有另一个对应的因子,观察可得,它们的分布是平均的,左边的一半对应右边的一半,那么最中间的分界线应该是什么? $\sqrt{n}$。

因此,我们只需要对$\sqrt{n}$前面的数字进行判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include<stdio.h>

# include<string.h>

# define maxn 1000000+10

int pri[maxn];
int isprime(int n)
{
for(int i=2;i*i<=n;i++)//只需要将i变成i*i即可
if(n%i==0)
return 0;
return 1;
}
int main()
{
pri[1]=0;
for(int i=2;i<maxn;i++){
pri[i]=isprime(i);
}
return 0;
}

这种算法的复杂度要比上一种好的多,复杂度为$O(n\sqrt{n})$,但是对于1e6的数据范围来说还是太大了。有没有再快一点的算法?

3.素数筛选法

素数筛选法的思想为:

从2开始,因为2的倍数一定不是素数,所以先把2的倍数全部删去;

接着找下一个素数3,把3的倍数全部删去;

因为4是2的倍数,已经被删去,所以直接找下一个素数5,把5的倍数全部删去;

接着7的倍数,11的倍数,……直到把1e6范围内的合数全部筛选出去,剩下的即为素数:

//以下优化均基于打表的基础上

1
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
# include<stdio.h>

# include<string.h>

# define maxn 1000000+10

int vis[maxn];
void isprime()
{
memset(vis,0,sizeof(vis));//此处vis[i]=1表示不是素数,vis[i]=0表示是素数
vis[1]=1;
//由于i*i的数据范围可能会超过int,所以需要用long long表示
for(long long i=2;i*i<=maxn;i++){//此处有优化,因为如果一个合数>sqrt(maxn),那么他必定在前面已经被标记过。
if(!vis[i]){
for(long long j=i*i;j<=maxn;j+=i){//此处也有优化,我们只需要判断从i*i开始判断即可。
vis[j]=1;
}
}
}
}
int main()
{
int n;
isprime();
return 0;
}

这种算法的复杂度应该为O(n);,是一种非常快速的判断素数的算法。

上述代码有两处优化,第一处优化的证明如下:

假设 maxn > i > sqrt(maxn)并且为合数,那么,他肯定会有一个因子小于等于sqrt(maxn),因此,i一定在之前已经被标记过了。

第二处优化证明为:

假设i>2,那么对于 i * ( i - 1 ):

如果 i - 1是素数,那么 i * ( i - 1 ) 一定在之前已经被标记过;

否则,如果 i - 1 是合数,那么 i - 1能被分成更小的素数。设其中一个为a,那么 i ( i - 1 )= i ( i - 1 ) / a * a 也一定被标记过。

优化后的算法时间会节省非常多,在平常的算法竞赛中,用上述代码就已经可以解决大部分的涉及素数打表的问题。

感谢您的支持
-------------本文结束感谢您的阅读-------------