3098779_wa.cc

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

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.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;
	char ll[10000], uu[10000];

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