3511.cpp

北大acm上的第3511题

#include"stdio.h"
#include"math.h"
#include"vector"
#include"iostream"
#define N  1000000
using namespace std;
vector<bool> a(N + 1, true);


int main()
{ 

   int i;int k=1;

    vector<int> arimes;
    int Time = 0;
    for (int I = 2; I <= N; I++)
    {
        if (a[I])
        {
            arimes.push_back(I);
        }
        for (int J = 0; J < (int)arimes.size() && I * arimes[J] <= N; J++)
        {
            a[I * arimes[J]] = false;
            if (I % arimes[J] == 0) break;//关键一句，防止重复标记
        }
    }
	int  l,u,x,y;int  le,ri;int mid;
	while(scanf("%d %d",&l,&u)&&!(l==-1&&u==-1))
	{
            le=0;ri=arimes.size();x=0;y=0;
		    while(le<ri)
			{
				mid=(le+ri)/2;
				if(arimes[mid]<l)
				{
					le=mid+1;
				}
				else if(arimes[mid]>l)
					ri=mid-1;
				else break;
			}
           i=mid-2;
		   if(i<0)i=0;
			while(arimes[i]<=u&&i<arimes.size())
			{
				if(arimes[i]>=l)
				{
					x++;
					if(arimes[i]%4==1||arimes[i]==2)
						y++;
				}
				i++;

			}
			printf("%d %d %d %d\n",l,u,x,y);
	}


	return  1;
}