POJ 3292

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <math.h>
#define INF 0x3f3f3f3f
using namespace std;

int has[1000002];
int main()
{
    int h;
    memset(has,0,sizeof(has));
    for(int i=5; i<=1000001; i+=4)
    {
        for(int j=5; j<=1000001; j+=4)
        {
            h=i*j;
            if(h>1000001)
            {
                break;
            }
            if( has[i]==0 && has[j]==0)
            {
                has[h]=1;
            }
            else
            {
                has[h]=-1;
            }
        }
    }
    int sum=0;
    int pri[1000002];
    for(int i=1;i<=1000001;i++)
    {
        if(has[i]==1)
        {
            sum++;
        }
        pri[i]=sum;
    }
    int n;
    while(~scanf("%d",&n)&&n)
    {
        printf("%d %d\n",n,pri[n]);
    }
    return 0;
}