题意
定义所有形如 4*k+1 (k为正整数) 的数字为h数,如1,5,9,13,17,21,……。
定义在h数集中仅能用1与本身乘积表示的数(不包括1)为h素数。
定义在h数集中可以表示为两个h素数乘积表示的数为h半素数。
试求有多少小于等于给定h数的h半素数。
思路
暴力预处理,直接查询输出。
代码
#include <stdio.h>
int n=1000001,x,h[1000005];
int main()
{
for (int i=5;i<=n;i+=4)
for (int j=5;j<=n&&i*j<=n&&i*j>0;j+=4)
{
if (h[i]==0&&h[j]==0) h[i*j]=1;
else h[i*j]=-1;
}
int cnt=0;
for (int i=1;i<=n;h[i++]=cnt)
if (h[i]==1) cnt++;
while (scanf("%d",&x),x!=0) printf("%d %d\n",x,h[x]);
}