2396225_wa.c

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

#include <stdio.h>
#include <string.h>
int a[1000003], b[100000];
int no;

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;
	}
	b[no] = 10000000;
	while(scanf("%d",&n)==1,n)
	{
		printf("%d ",n);
		for(i = 0; b[i] <= n; i++);
		printf("%d\n",i);
	}
	return 1;
}