欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

素数筛选法

程序员文章站 2024-03-15 15:11:45
...

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

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

1.按照定义计算

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

#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

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

因此,我们只需要对√n 前面的数字进行判断即可。

#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√n),但是对于1e6的数据范围来说还是太大了。有没有再快一点的算法?

3.素数筛选法

素数筛选法的思想为:

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

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

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

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

//以下优化均基于打表的基础上
 
#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 也一定被标记过。

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