数论训练之一

http://www.codevs.cn/problem/3223/

L,R的范围太大了,不可能直接筛素数

但考虑到R-L的范围在能承受的范围内,

这时候就要用到

区间筛:

主体思想与其他筛法一致,

但一般题目中数据范围比较大(L<R<=10^12),但也有个利于我们的限制条件(R-L<=10^6)

那就很简单了,根据我们熟知的理论,

R以内的合数的最小质因数不会大于√R,

所以我们就可以筛出[1,√R]内的素数并用这些素数去筛除[a,b]的合数。

code:

#include<iostream>
#include<cstdio>
using namespace std;
long long l,r,ans;
bool f1[1000010],f2[1000010];
inline void ask(long long a,long long b)
{
    for(long long i=2;i*i<=b;i++)
    {
        if(!f1[i])
        {
            for(long long j=2*i;j*j<=b;j+=i)f1[j]=1;
            for(long long j=max(2LL,(a+i-1)/i)*i;j<=b;j+=i)
                f2[j-a+1]=1;
        }
    }
    for(long long i=1;i<=b-a+1;i++)
        if(!f2[i])
            ans++;
}
int main()
{
    scanf("%lld%lld",&l,&r);
    ask(l,r);//区间筛 
    printf("%d",ans);
}
上一篇:[洛谷P1972][题解][SDOI2009]HH的项链


下一篇:2.3 salt 初始化系统