10140 - Prime Distance

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1081

Solution Idea : Sieve then segmented sieve.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool status[101000];

vector<int>prime;

void sieve()
{
    int n=sqrt(2247483647);
    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;

    prime.push_back(2);

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

int arr[1000003];

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

    if(a==1) a++;

   ll int sq=sqrt(b);

    for(ll int i=0;i<prime.size() and prime[i]<=sq;i++)
    {
        ll int p=prime[i];
       ll 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;
        }

    }
    ll int c1=0,c2=0,d1=0,d2=0,mn=1000000000,mx=-1,cnt=0,c11=0,c22=0,d11=0,d22=0;

    for(ll i=a;i<=b;i++)
    {
        if(arr[i-a]==0 and cnt%2==0) {
                c1=i;
                cnt++;
        }
        else if(arr[i-a]==0 and cnt%2!=0) {
                c2=i;
                cnt++;
                i--;
                if(c2-c1<mn)
                {
                    mn=c2-c1;
                    c11=c1;
                    c22=c2;
                }
        }
    }
    cnt=0;
      for(ll i=a;i<=b;i++)
    {
        if(arr[i-a]==0 and cnt%2==0) {
                d1=i;
                cnt++;
        }
        else if(arr[i-a]==0 and cnt%2!=0) {
                d2=i;
                cnt++;
                i--;
                if(d2-d1>mx)
                {
                    mx=d2-d1;
                    d11=d1;
                    d22=d2;
                }
        }
    }
    if(c22!=0) printf("%lld,%lld are closest, %lld,%lld are most distant.\n",c11,c22,d11,d22);
    else printf("There are no adjacent primes.\n");


}



int main()
{
    sieve();

ll int a,b;

    while(scanf("%lld%lld",&a,&b)==2)
    {

    sgmnt_sieve(a,b);

    }


}