Fermat's Chirstmas Theorem ( UVALive 4088, Regionals 2007 >> Africa/Middle East - Arab and North Africa)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 1000005

bool stats[MX];
vector<int>prime;
vector<int>sqp;


void PrimeGenerate(int n)
{
    int sq=sqrt(n);
    for(int i=3; i<=sq; i+=2)
    {
        if(!stats[i])
            for(int j=i*i; j<=n; j+=i+i)
                stats[j]=true;
    }
    for(int i=2;i<=n;i+=2) stats[i]=true;

    prime.push_back(2);
    for(int i=3; i<=n; i+=2)
        if(!stats[i])
            prime.push_back(i);
return;
}

void squareRootGen(int n)
{
    int sq=sqrt(n);
    for(int i=1;i<=sq;i++)
        for(int j=i+1;j<=sq;j+=2)
        {
            int mul=i*i+j*j;
            if(mul>1000000) break;
            if(!stats[mul])
                sqp.push_back(mul);
        }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, L, U, x, y;
    string s;
    char ch;
    PrimeGenerate(1000000);
    squareRootGen(1000000);
    sqp.push_back(2);
    sort(sqp.begin(), sqp.end());
    while(cin>>L>>U)
    {
        if(L==-1 && U==-1) break;
        int x = upper_bound(prime.begin(), prime.end(), U) - lower_bound(prime.begin(), prime.end(), L);
        int y = upper_bound(sqp.begin(), sqp.end(), U) - lower_bound(sqp.begin(), sqp.end(), L);
        cout<< L <<" "<<U<<" "<<x<<" "<<y<<"\n";
    }
return 0;
}