先筛选求素数了,存下500000内的素数然后打表把1000000内的半素数都求出来了。巨麻烦。求简单解法。

#include <stdlib.h>
#include <stdio.h>
int p[2000000]={0},cp[500005]={1,1},sp[1000005]={0};
int main()
{
long i,j,k,n;
for(i=2;i<1000;i++)
for(j=i*i;j<500000;j+=i)
cp[j]=1;
j=0;
for(i=2;i=0;i–)
for(k=0;p[i]*p[k]<1000000;k++)
sp[p[i]*p[k]]=1;
while(scanf(“%ld”,&n)!=EOF){
if(sp[n]==1)
printf(“Yes\n”);
else
printf(“No\n”);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation