3098670_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>

int prime[1000009], cnt;
int num[80000];

void init()
{
	int i, j;

	memset(prime,0,sizeof(prime));
	cnt = 2;
	num[0] = 1;
	num[1] = 2;
	for(i = 3; i <= 1000000; i+=2)
	{
		if(prime[i]==0)
		{
			num[cnt++] = i;
			for(j = i+i; j <= 1000000; j+=i)
			{
				prime[j] = 1;
			}
		}
	}
}

int main()
{
	int i, l, u;
	int L, U;

	init();
	while(scanf("%d%d",&l,&u)==2)
	{
		L = l;U = u;
		if(l==-1&&u==-1)
		{
			break;
		}
		if(l < 0)
			l = 0;
		if(u > 1000000)
			u = 1000000;
		int x, y;
		x = y = 0;
		for(i = 1; i < cnt && num[i] <= u; i++)
		{
			if(num[i]>=l)
			{
				x++;
				if(num[i]%4==1)
					y++;
			}
		}
		printf("%d %d %d %d\n",L,U,x,y);
	}
	return 0;
}