2396457_ac_640ms_15876k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 51 行

#include <stdio.h>
#include <string.h>
__int64 a[1000003], b[1000000];
int no;
__int64 c[1000003];
int check(int num)
{
	int i;

	for(i = 5; i < num/4; i+=4)
		if(num%i==0&&(num/i)%4==1)
			return 1;
	return 0;
}

int main()
{
	int n, j, i;

	no = 0;
	memset(a,0,sizeof(a));
	for(i = 5; i*i<=1000001; i+=4)
	{
		for(j = i; i*j<=1000001; j+=4)
			a[i*j] = 1;
	}
	for(i = 5; i <= 1000001; i+=4)
	{
		if(5*i>1000001)
			break;
		if(!a[i])
			b[no++] = i;
	}
	memset(c,0,sizeof(c));
	int tt = 0;
	for(i = 0; i < no; i++)
		for(j = i; j<no&&b[i]*b[j] <= 1000001; j++)
		{
			c[b[i]*b[j]] = 1;
		}
	for(i = 5; i <= 1000001; i+=4)
		if(c[i])
			a[tt++] = i;
	while(scanf("%d",&n)==1,n)
	{
		printf("%d ",n);
		for(i = 0; i<tt&&a[i] <= n; i++);
		printf("%d\n",i);
	}
	return 1;
}