Deepak and prime second

#1

question link - https://hack.codingblocks.com/contests/c/547/760
my solution link -: https://ide.codingblocks.com/s/96796

getting TLE in the last test case.
anyone, please help to resolve this.

#2

@Saurabh-Kumar-1331476656958199

#3

in segmented seive you are iterating every element in l to r and checking … it is multiple of prime or not… you just need to go on multiple of prime …i.e i+=prime in l to r

#4 
for(ll j=0;j<primeUpToRootN.size();j++)
{
    //cout<<primeUpToRootN[j]<<endl;
    if(m<primeUpToRootN[j]*primeUpToRootN[j])
    {
        break;
    }
    for(ll i=n;i<=m;i++)
    {
        if(i==1)
        {
            arr[i-n]=0;
        }
        if(i%primeUpToRootN[j]==0 && i!=primeUpToRootN[j])
        {
           // cout<<i<<endl;
            arr[i-n]=0;
        }
        
    }
}

in this part i++ will not work… just do as in normal seive we do i+=(some prime)

#5 
`for(ll j=0;j<primeUpToRootN.size();j++){
    //cout<<primeUpToRootN[j]<<endl;
    if(m<primeUpToRootN[j]*primeUpToRootN[j]){
        break;
    }
    ll k=(n/primeUpToRootN[j])*primeUpToRootN[j];
    if(n%primeUpToRootN[j]!=0){
        k=k+primeUpToRootN[j];
    }
    for(ll i=k;i<=m;i += primeUpToRootN[j]){
        if(i==1){
            arr[i-n]=0;
        }
       
        if(i%primeUpToRootN[j]==0 && i!=primeUpToRootN[j]){
           // cout<<i<<endl;
            arr[i-n]=0;
        }
        // i= i+primeUpToRootN[j]-(i%primeUpToRootN[j]);
        
    }
}`
#6

i tried this first jump to first multiple then increase by that prime number but now all testcase are wrong

#7

see my code for better understanding how to implement it…

#8 
 int l,r;
 cin>>l>>r;
 
 int rr=sqrt(r);
 memset(a,0,sizeof(a));

 for(auto x:prime)
 {
      if(x>rr) break;

      int start=(l+x-1)/x;
      start*=x;

      for(int i=start-l; i<=r-l; i+=x)
      {
           if(i+l!=x) a[i]++;
      }
 }
 for(int i=0;i<=r-l;i++)
      if(!a[i] && i+l!=1) cout<<i+l<<endl;
#9

prime is a vector which contains prime numbers till 1e6.

#10

thanks a lot for help.