LightOj 1197 Help Hanzo Solution

 

Problem Link:  https://lightoj.com/problem/help-hanzo

Hints:   Here i just implement  basic Segmented Sieve 

 Solution in C++: 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include<bits/stdc++.h>

using  namespace  std;

typedef long long int ll;

vector<ll>prime;

void sieve()

{

    ll check[50000];

    memset(check,0,sizeof(check));

    for(int i=2; i*i<=50000; i++)

    {

        if(check[i]==0)

        {

            for(int j=i*i; j<=50000; j+=i)

            {

                check[j]=1;

            }

        }

    }

    prime.push_back(2);

    for(int i=3; i<=50000; i+=2)

    {

        if(check[i]==0)prime.push_back(i);

    }

}

int fss(ll a,ll b)

{

    ll sz=b-a+1;

    ll i,j,ans=0;

    sz=b-a+1;

    ll flag[sz+1];

    for(i=0; i<sz; i++)flag[i]=0;

    if(a<2)a=2;

    for(i=0; prime[i]*prime[i]<=b&&i<prime.size(); i++)

    {

        j=prime[i]*(a/prime[i]);

        if(j<a)

            j+=prime[i];

        if(j<prime[i]+prime[i])

            j=prime[i]+prime[i];

        for(; j<=b; j+=prime[i])

            flag[j-a]=1;

    }

    for(ll i=0; i<b-a+1; i++)

    {

        if(flag[i]==0)

        {

            ans++;

        }

    }

    cout<<ans<<endl;

}

int main()

{

    sieve();

    ll t,l,r;

    cin>>t;

    for(int i=1; i<=t; i++)

    {

        cout<<"Case "<<i<<": ";

        cin>>l>>r;

        fss(l,r);

    }

    return 0;

}