LightOJ 1197求大区间的素数个数

一时失言乱红尘 2024-04-17 05:52 71阅读 0赞

https://blog.csdn.net/strangedbly/article/details/50937591

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const ll maxn = 1e6+50;
    
    bool vis[maxn];
    ll pr[maxn];
    ll len = 0;
    bool visab[maxn];
    int cnt2;
    void Seve_prime()
    { 
    
        memset(vis, true, sizeof(vis));
        vis[0] = vis[1] = false;
        for(ll i = 2;i< maxn;i++)
        { 
            if(vis[i])
            { 
                cnt2++;
                pr[len++] = i;
                for(ll j = i*i;j <maxn;j+=i)
                { 
                    vis[j] = false;
                }
            }
    
        }
    }
    
    int main()
    { 
        ios_base::sync_with_stdio(false);
        Seve_prime();
        ll cnt = 0;
        ll T;
        cin>>T;
        cout<<cnt2<<endl;
        while(T--)
        { 
            cnt++;
            ll a, b, sum = 0;
            cin>>a>>b;
            if(b< maxn)
            { 
                for(ll i = a;i <= b;i++)
                { 
                    if(vis[i])sum++;
                }
    
            }
            else
            { 
                memset(visab, true, sizeof(visab));
                for(ll i = 0;i <len&& pr[i] <= b;i++)
                { 
                    ll k  = a/pr[i];
                    if(k*pr[i] < a)
                    { 
                        k++;
                    }
    
                    for(ll j = k*pr[i];j <= b;j+=pr[i])
                    { 
                        visab[j-a] = false;
                    }
                }
    
                for(ll i = a;i <=b;i++)
                { 
                    if(visab[i-a])
                    { 
                        sum++;
                    }
    
                }
    
            }
            cout<<"Case "<<cnt<<": "<<sum<<endl;
    
        }
    
        return 0;
    }