LightOJ 1197 Help Hanzo

Hints : Implement, Segmented Sieve Algorithm To Generate Prime Numbers. Here is a tutorial for segmented sieve. Bangla Tutorial Link: https://www.shawonruet.com/2016/10/segmented-sieve.html

#include <bits/stdc++.h>
using namespace std;
#define n 100005
vector<long long int>s,sg,segment;
long long int p[n],k=1,size;
bool a[n];
long long int prime()
{
    long long i,j;
    a[0]=a[1]=1;
    for(i=4;i<=n;i=i+2)
    {
        a[i]=1;
    }
    for(i=3;i<=sqrt(n);i=i+2)
    {
        for(j=i*i;j<=n;j=j+2*i)
        {
            a[j]=1;
        }
    }
    p[0]=2;
    for(i=3;i<=n;i=i+2)
    {
        if(a[i]==0)
        {
            p[k]=i;
            //cout<<p[k]<<endl;
            k++;
        }
    }


}

void segmented_sieve(long long int l,long long int u)
{
    long long int root,start,i,j,si;
    sg.clear();
    root=sqrt(u)+1;



    for(i=l;i<=u;i++)
    {
        sg.push_back(i);
    }


    if(l==0)
    {
        sg[1]=0;
    }
    else if(l==1)
    {
        sg[0]=0;
    }



    for(i=0;p[i]<=root;i++)
    {
        si=p[i];

        start=si*si;

        if(start<l)
        {
            start=((l+si-1)/si)*si;
        }


        for(j=start;j<=u;j=j+si)
        {
            sg[j-l]=0;

        }
    }

}

int main()
{
     long long int m,g,c,r,t,l,h,u,w,tc,tx,i,j,st;
     //freopen("1197in.txt","r",stdin);
     //freopen("1197out.txt","w",stdout);
     prime();
     cin>>tc;

     for(tx=1;tx<=tc;tx++)
     {

        cin>>l>>u;
        segmented_sieve(l,u);

        for(i=l;i<=u;i++)
        {


            if(sg[i-l]!=0)
            {
                segment.push_back(sg[i-l]);
            }
        }
        st=segment.size();
        printf("Case %lld: %lld\n",tx,st);
        segment.clear();
        sg.clear();




     }



    return 0;
}

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here