素数筛选法
素数,是指因子只包含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 也一定被标记过。
优化后的算法时间会节省非常多,在平常的算法竞赛中,用上述代码就已经可以解决大部分的涉及素数打表的问题。
上一篇: python学习第一天
下一篇: 求n以内的素数