两个点TLE，用的线性筛板子，应该复杂度正确。。。

#include<bits/stdc++.h>
using namespace std;
int a,b,p,prime[100010],cnt,pri[100010],ans;

void mkpr(int r)
{
    for(int i=2;i<=r;i++)
    {
        if(prime[i]==0)pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<r;j++)
        {
            prime[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}

struct bcj
{
    int fa[100010];
    void init(int l,int r)
    {
        for(int i=l;i<=r;i++)fa[i]=i;
    }
    int find(int x)
    {
        if(fa[x]==x)return x;
        return find(fa[x]);
    }
    void unite(int x,int y)
    {
        int u=find(x),v=find(y);
        if(u!=v)fa[u]=v;
    }
}d;
int ceill(int x,int y)
{
    if(x/y*y==x)return x/y;
    return x/y+1;
}
int main()
{
    cin>>a>>b>>p;
    d.init(a,b);
    mkpr(b+1);
    int k=0;
    for(int i=1;i<=cnt;i++)if(pri[i]<p)k++;
    k++;
    for(int i=k;i<=cnt;i++)
    {
        int l=ceill(a,pri[i]);
        for(;pri[i]*(l+1)<=b;l++)d.unite(pri[i]*l,pri[i]*(l+1));
    }
    for(int i=a;i<=b;i++)ans+=(int)(d.fa[i]==i);
    cout<<ans;
    return 0;
}