2396121_wa.c

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

#include <stdio.h>
#include <string.h>
int a[1000003], b[1000000];
int no;
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]++;
	}
	for(i = 5; i <= 1000001; i+=4)
	{
		if(a[i]==1)
			b[no++] = i;
	}
	while(scanf("%d",&n)==1,n)
	{
		printf("%d ",n);
		for(i = 0; i<no&&b[i] <= n; i++);
		printf("%d\n",i);
	}
	return 1;
}