当你的才华
还撑不起你的野心时,那你就应该静下心来学习

欧拉筛法

欧拉筛法


素数就是指不能被除了1和自身以外的别的数整除的数,比如2,3,5,而且根据欧几里得的证明来看,素数是无限的,普通的筛选素数的方法可能对较小的数据能在较短时间内完成筛选,但对于很大的数据(比如1e9)就会花费很长的时间。

例如,普通的求素数方法时这样的:

int pri[MAXN];
int cnt=0;
void prime(int n)
{
    cnt=0;
    pri[cnt++]=2;
    int i,j;
    for(i=3;i<=n;++i)
    {
        for(j=2;j<i;++j)
        {
            if(i%j!=0)
                break;
        }
        if(j>=i)
            pri[cnt++]=i;
    }
}

根据素数的定义所写的代码很容易理解,但是运行的效率是不太优秀的,所以我们要改进,当然在学习的过程中相信大家也或多或少的学了些改进方法,一个简单的改进方法就是将第二个循环的结束条件改为j<sqrt(i),相应地再更改判断条件,这样当然可以减少我们运行所需要的时间,但是任然不够好,下面我们就来介绍一下埃式筛法和今天的真正目标——欧拉筛法。

先来介绍埃式筛法,埃式筛法的基本思想就是,当我们遍历到一个素数时,把所有该素数的倍数(自然是合数)都筛选出来,我们来看看代码:

int prime[MAXN];
bool vis[MAXN];
int cnt=0;
void Era_peime(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!vis[i])
            prime[cnt++]=i;
        for(int j=i;j<=n;j+=i)
        {
            vis[j]=true;
        }
    }
}
int visit[maxn];  
void Prime(){
    mem(visit,0);           //初始化都是素数
    visit[0] = visit[1] = 1;  //0 和 1不是素数
    for (int i = 2; i <= maxn; i++) {
        if (!visit[i]) {         //如果i是素数,让i的所有倍数都不是素数
            for (int j = i*i; j <= maxn; j += i) {
                visit[j] = 1;
            }
        }
    }

当我们有没被选过的素数时,加入素数数组prime并且将它的所有n以内的倍数给筛选出来(vis[j]=true),埃式筛法很容易理解,并且在效率上也比较优秀,时间复杂度为O(nlglgn), 但是在处理1e8以上的数据时,还是稍稍力不从心,所以接下来我们着重介绍下线性时间筛法——欧拉筛法,我们还是先来看下代码:

int prime[MAXN];
bool vis[MAXN];
int cnt=0;
void Euler_peime(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!vis[i])
        {prime[cnt++]=i;vis[i]=true;}//vis[i]置为true或不置true都可以
        for(int j=0;j<cnt;++j)
        {
            if(i*prime[j]>n)//判断是否越界
                break;
            vis[i*prime[j]]=true;//筛数
            if(i%prime[j]==0)//时间复杂度为O(n)的关键!
                break;
        }
    }
}
int prime[maxn];
int visit[maxn];
void Prime(){
    mem(visit,0);
    mem(prime, 0);
    for (int i = 2;i <= maxn; i++) {
        cout<<" i = "<<i<<endl;
        if (!visit[i]) {
            prime[++prime[0]] = i;      //纪录素数, 这个prime[0] 相当于 cnt,用来计数
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

我们注意到,在用埃式筛法的同时,同一个数字也许会被筛选多次,比如6先被2筛选一次,再被3筛选一次,这样就浪费了很多不必要的时间,而欧拉筛法通过if(i%prime[j]==0)break;

这一步就避免了重复筛选的发生,我们举个例子,比如,2先筛选了4,然后进行下一个循环,3筛选6和9,当我们执行到4的时候,可以发现,当i==4时,第一次运行到if(i%prime[j]==0)这一步的时候就直接break;掉了,这也就是说,当我们的合数进入循环时,其实它已经被之前的数筛选过了,所以当合数进入内层循环时,内层循环只执行了一次,从而减少了时间复杂度。

赞(4) 打赏
未经允许不得转载:啾啾鸟 » 欧拉筛法

欢迎来到Birdjiujiu

欢迎刷题

阿巴阿巴阿巴

微信扫一扫打赏