杭电2098 Time Limit Exceeded http://acm.hdu.edu.cn/showproblem.php...
发布网友
发布时间：2024-10-19 19:11
共1个回答
热心网友
时间：2024-10-24 07:06
4041339 2011-06-03 19:48:04 Accepted 2098 156MS 208K 484 B C daijiu123
上面说明我下面的代码已经AC，你的主要问题出在算法，判断素数上，虽然正确，但太耗时，比如判断m是不是素数，只要判断从2到（根号m）都不能整除m即可，不必从2到m
#include <stdio.h>
#include <math.h>
int main()
{
int i,m,l=0,a[500],b[500],flag1=1,flag2=1,j,k,q,s;
while(scanf("%d",&a[l])&&a[l]!=0) l++;
for(m=0;m<l;m++)
{
s=0;
for(i=2;i<(float)a[m]/2;i++)
{
flag1=flag2=1;
for(j=2;j<=sqrt(i);j++) if(i%j==0) {flag1=0;break;}
if(flag1)
{
k=a[m]-i;
for(q=2;q<=sqrt(k);q++) if(k%q==0) {flag2=0;break;}
if(flag2) s++;
}
}
b[m]=s;
}
for(i=0;i<l;i++) printf("%d\n",b[i]);
return 0;
}
