线性筛素数

· · 个人记录

筛法：

利用唯一分解定理，用已筛出来的素数作为因子，乘上其他的数将后面的指定范围的并且因子中包含这些素数的合数标记，则完成后所有未标记的数即为素数。

线性筛：

通过最朴素的筛法可以发现，一个合数总会被每个素数因子筛一遍，因此如果保证每个合数只被筛一遍，时间就可以变为线性。所以我们用每一个合数的最小质因子来筛，使每个合数只被筛一次。

方法：

求n以内的素数

设：

数组v[i]表示数i的最小素因子；

变量m表示当前已求得的素数个数；

p数组保存当前求得的素数；

循环i从2到n

1、 当当前的数i没有标记（v[i]=0）时，则这个数为素数（因为数i假如是合数，则它的最小素因数一定在2~i-1的范围内，在之前就会筛掉i），p[++m]=i；

2、循环j从1到m，用i乘上当前求出的素数p[j]来筛后面的合数，

当v[i]>=p[j]时，v[i*p[j]]=p[j];

(v[i]为i的最小素因子，则 i*p[j] 这个数的最小素因子为p[j])

当v[i]<p[j]或i*p[j]大于范围n时，便退出循环,

代码：

for(int i=2; i<=r; i++)
{
  if (v[i]==0) 
  {
     v[i]=i; 
     ++m; 
     p[m]=i;
   }
  for(int j=1; j<=m; j++)
  {
    if (p[j]*i>r||p[j]>v[i]) break;
    v[p[j]*i]=p[j];
  }
}

求l~r范围内的素数：

当r>100000000时筛选1~r的素数，即使线性筛也会超时； 但我们知道l~r范围内的数的最小质因子不会超过根号r；

所以可以筛出1~根号r的素数，再用这些素数去筛l~r的合数；

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>

using namespace std;

long long l,r,v[1000010],p[1000010],m,num,ans;
bool f[1000010];

int main()
{
    scanf("%lld%lld",&l,&r);
    long long rr=sqrt(r)+1;
    for(int i=2; i<=sqrt(r)+1; i++)
    {
      if (v[i]==0) 
      {
         v[i]=i; 
         ++m; 
         p[m]=i;
      } 
      for(int j=1; j<=m; j++)
      {
        if (p[j]*i>rr||p[j]>v[i]) break;
         v[p[j]*i]=p[j];
      }

     }
     for(int i=1; i<=m; i++)
     {
        for(int j=l/p[i]; j*p[i]<=r; j++)
         {
            if (j*p[i]>=l&&j*p[i]!=p[i]) f[j*p[i]-l]=true;
         }
     } 
     for(int i=l; i<=r; i++) if (!f[i-l]) ++ans; 
     if (l==1) ans--;
       printf("%lld\n",ans);
    return 0;
}

我的线性筛学习于算法竞赛进阶指南