3157485_ac_110ms_15072k.c

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

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

int comp[1300000];
int cnt;
int prime[1300000], ans[1300000];

void init()
{
	int i, j, tmp;

	memset(prime,0,sizeof(prime));
	for(i = 3; i <= 1300000; i+=2)
	{
		if(prime[i]==0)
		{
			for(j = i+i; j <= 1300000; j+=i)
			{
				prime[j] = 1;
			}
		}
	}
	cnt = 0;
	for(i = 4; i <= 1300000; i++)
	{
		if(i%2==0)
			comp[cnt++] = i;
		else
		{
			if(prime[i]==1)
			{
				comp[cnt++] = i;
			}
		}
	}
	for(i = 0; i < cnt; i++)
	{
		tmp = 1;
		j = i+1;
		while(j < cnt&&comp[j]==comp[j-1]+1)
		{
			tmp++;
			j++;
		}
		tmp++;
		while(i < j)
		{
			ans[comp[i]] = tmp;
			i++;
		}
		i--;
	}
}

int main()
{
	int n;

	init();
	while(scanf("%d",&n)==1,n)
	{
		if(prime[n]==0)
			puts("0");
		else
			printf("%d\n",ans[n]);
	}
	return 0;
}