Segmented Sieve Source Code

#include<bits/stdc++.h>

using namespace std;

bool status[1010000];

vector<int>prime;

void sieve()
{
    int n=1000100;
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i;j<=n;j=j+(2*i)) status[j]=true;
        }
    }
    status[0]=true;
    status[1]=true;

    for(int i=2;i<=n;i++)
    {
        if(status[i]==false) prime.push_back(i);
    }
}

int arr[100010];

int sgmnt_sieve(int a,int b)
{
    memset(arr,0,sizeof(arr));

    if(a==1) a++;

    int sq=sqrt(b);

    for(int i=0;i<prime.size() and prime[i]<=sq;i++)
    {
        int p=prime[i];
       long long  int j=p*p;

        if(j<a) j=((a+p-1)/p)*p;

        for(;j<=b;j=j+p)
        {
            if(j<0) break;
            arr[j-a]=1;
        }

    }
    int cnt=0;

    for(int i=a;i<=b;i++)
    {
        if(arr[i-a]==0) cnt++;
    }

   return cnt;
}

int main()
{
    sieve();

int a,b,t,ca=1;
cin>>t;
    while(t--)
    {
           cin>>a>>b;
    cout<<"Case "<<ca<<": "<<sgmnt_sieve(a,b)<<endl;
ca++;
    }
}