UVa 11408 - Count DePrimes

// Accepted
// Seieve, DP

#include<bits/stdc++.h>

using namespace std;

#define high 5000010
#define sf scanf
#define pf printf

typedef long long LL;
typedef vector<LL>vl;

bitset<high>bs;

LL ar[high];

LL prime[(high>>6) + 1];
vl prm;

#define setbit(n) (prime[n>>6] |= (1 << ((n >> 1) & 31)))
#define checkbit(n) (prime[n>>6] & (1 << ((n >> 1) & 31)))

void sieve()
{
    LL i,j;

    for(i=3; i*i<high; i+=2)
    {
        if(!checkbit(i))
        {
            for(j=i*i; j<high; j+=(2*i))
            {
                setbit(j);
            }
        }
    }

    prm.push_back(2);

    for(i=3; i<high; i+=2)
    {
        if(!checkbit(i))
        {
            prm.push_back(i);
        }
    }

    //for(i=0; i<100; i++)cout << prm[i] << " ";
    //cout << prm[prm.size()-1];
    //cout << prm.size();
}

void deprimes()
{
    LL i,j;

    bs.set();

    ar[2] = 2;

    for(i=4; i<high; i+=2)
    {
        ar[i] = 2;
        bs[i] = 0;
    }

    bs[2] = 0;

    for(i=3; i<high; i++)
    {
        if(bs[i])
        {
            ar[i] = i;

            for(j=2*i; j<high; j+=i)
            {
                ar[j]+=i;
                bs[j] = 0;
            }
        }
    }

    //for(i=4; i<=20; i++) cout << i << "-" << ar[i] << "\n";
}

bool isPrime(LL n)
{
    if(n==2) return true;

    if(n<2) return false;

    if(n!=2 and !(n&1)) return false;

    if(n < high) return !checkbit(n);

    for(LL i=0; i<prm.size() and prm[i]*prm[i]<=n; i++)
    {
        if(!(n%prm[i])) return false;
    }

    return true;
}

LL b_search(LL lo, LL hi, LL item)
{
    if(lo > hi) return -1;

    LL mid = (lo + hi)/2;

    if(prm[mid] == item) return mid;

    if(prm[mid] > item) return b_search(lo, mid-1, item);
    else return b_search(mid+1, hi, item);
}

LL ans[high];

void check_deprimes()
{
    for(LL i=2; i<high; i++)
    {
        LL r = b_search(0, prm.size()-1, ar[i]);

        //cout << i << "-" << ar[i] << "-" << prm[r] << "\n";

        if(prm[r] == ar[i])
        {
            ans[i] = 1 + ans[i-1] ;
        }

        else
        {
            ans[i] = ans[i-1];
        }

        //cout << ans[i] << "\n";
    }
}

int main()
{
    sieve();
    deprimes();
    check_deprimes();

    LL x,y;

    while(~sf("%lld", &x))
    {
        if(!x) break;

        sf("%lld", &y);

        //cout << ans[x-1] << " " << ans[y] << "\n";
        pf("%lld\n", ans[y] - ans[x-1] );
    }

    return 0;
}