~~**裸的筛法大家应该都会**~~**但是裸的筛法貌似没法用了怎么办呢?**
其实有个东西叫Miller-Rabbin,貌似是一个基于概率的算法,反正能用~~一些神奇的操作~~判断出当前这个数是不是质数,是不是感觉和普通筛法的某一步有点相似——如果这个数是质数那么就筛去这个数的倍数,但是如果这个数没被筛过还是得用神奇的Miller-Rabbin判断一下。~~关于神奇的Miller-Rabbin请查询百度~~
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int prime[3]={2,7,61};
bool yes[1000003];
long long pow(long long a,long long b,long long mod)
{
long long cnt=1;
a=a%mod;
while (b)
{
if (b&1) cnt=cnt*a % mod;
b>>=1;
a=a*a%mod;
}
return cnt;
}
bool MR(long long x)
{
long long r,q=0,cnt,tot;
if (x<2) return false;
for (int i=0;i<3;i++)
{
if (x==prime[i]) return true;
if (x%prime[i]==0) return false;
}
r=x-1;
while (!(r&1))
{
r>>=1;
q++;
}
for (int i=0;i<3;i++)
{
tot=q;
cnt=pow(prime[i],r,x);
while (tot)
{
if (cnt*cnt%x==1 && cnt!=1 && cnt!=x-1) return false;
cnt=cnt*cnt%x;
tot--;
}
if (cnt%x!=1) return false;
}
return true;
}
long long l,r,ans;
int main()
{
memset(yes,true,sizeof(yes));
scanf("%lld%lld",&l,&r);
for (long long i=l;i<=r;i++)
{
if (!yes[i-l+1]) continue;
if (MR(i))
{
long long j=i+i;
while (j<=r)
{
yes[j-l+1]=false;
j=j+i;
}
ans++;
}
}
printf("%lld\n",ans);
return 0;
}
```