Question

杭电acm 2012题目为什么老是WA呢。。求解答。。谢谢。。

#include <stdio.h>
#include <math.h>

int main(){

int star,end;
int i,j,temp;
int flag=0;

while(scanf("%d%d",&star,&end)!=EOF)
{

if(star==0 &&end == 0) break;

else if(star>end){temp=star;star=end;end=temp;}

for(i=star;i<=end;i++)
{
temp=i*i+i+41;
for(j=2;j<=temp/2;j++)
{
if(temp%j==0)
{
flag=1;
break;
}
}
if(flag==1)
break;
else
continue;
}
if(flag==1)
printf("Sorry\n");
else
printf("Ok\n");
flag=0;

}
return 0;
}

Answer 1

两个问题，一个是for(j=2;j<=temp/2;j++)里面，判断到sqrt(temp*1.0)就行了，也就是for(j=2;j<sqrt(temp*1.0);j++)，另外一个就是输出OK的K要大写。

这题的话，其实在这个区间里面运算结果不是素数的数只有3个，41、44、49，你只需要判断这三个数会不会出现在输入的区间里就行了，你原先的代码要是输入的包含40这个数，也会输出Sorry。

追问

首先谢谢。。我知道用sqrt (temp*1.0)的速度更快/更好，可是我用temp/2 判断的范围要比用sqrt (temp*1.0)来的大，为什么输入包含40时，我得到的数会是Sorry 呢？？

追答

不好意思，可能是杭电OJ的测试数据比较弱，刚算了下不是素数的数字有4个，包括40，所以有40的也应该输出Sorry，上次只判断了3个就AC了，可以算个小bug吧。。。你的算法没有问题，k换成大写就能通过了，不过为了效率高一点最好打表处理，这样时间复杂度立马小了，呵呵，祝你好运啦

Answer 2

具体问题他们都说了，我给楼主发一个AC了个代码供楼主参考吧！~

#include<stdio.h>
#include<math.h>
sushu(int n)
{
int i;
if(n==1)
return 0;//1是既不是素数也不是合数
if(n&1)//n wei jishu
{
for(i=3;i<=sqrt(1.0*n);i+=2)//sqrt 用浮点型
if(n%i==0)
return 0;//else 不能return 1；要最后return 1；因为return 1就直接结束函数了。
}
else//n wei oushu
return 0;
return 1;
}
main()
{
int x,y,n,flag;
while(scanf("%d %d",&x,&y)&&x!=0||y!=0)
{
flag=1;
for(n=x;n<=y;n++)
if(sushu(n*n+n+41)==0)
{
flag=0;
break;
}
if(flag)
printf("OK\n");
else
printf("Sorry\n");
}
return 0;//主函数是int型，要加return 0；另外acm的话，尽量主函数用int的，void型的有时候会编译不通过，原因我也不知道，但是习惯用int比较好。
}

还有一个取巧的做法：
#include<stdio.h>
main()
{
int x,y,n,flag;
while(scanf("%d %d",&x,&y)&&x!=0||y!=0)
{
flag=1;
if(x>=y||x<-39||y>50)continue;
for(n=x;n<=y;n++)
if(n==40||n==41||n==44||n==49)//打表得仅当n为这四个数时该算式值不为素数
{
flag=0;
break;
}
if(flag)
printf("OK\n");
else
printf("Sorry\n");
}
}

Answer 3

思路没有问题, 估计是错把"OK" 写成 "Ok"的缘故。