Posted on 2009-08-24 20:22
Uriel 阅读(447)
评论(0) 编辑 收藏 引用 所属分类:
POJ
这题做了一晚上。。TLE 10+次。。第二天优化了下，对于满足4C+1的数也事先存起来，最后减一下就行，瞬间32Ms。。
幸运的是组队赛时碰上了这题
/**//*Problem: 3511 User: Uriel
Memory: 12188K Time: 32MS
Language: C Result: Accepted*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int prime[80000],record[1000001],lenPr,i,j,sum1,sum2,L,U,k,sum[1000001],flag[1000001];
int main()
{
memset(record, 0, 4000004);
lenPr=0;
record[0]=1;
record[1]=1;
sum[0]=0;
sum[1]=0;
flag[0]=0;
flag[1]=0;
for (i = 2; i <=1000000; i++)
{
if (record[i]==0)
{
lenPr++;
prime[lenPr-1]=i;
}
for(j=0;j<=lenPr-1;j++)
{
if (i*prime[j]>1000000)
break;
record[i*prime[j]] = 1;
if (i%prime[j]==0)
break;
}
if(record[i]==0)sum[i]=sum[i-1]+1;
else
sum[i]=sum[i-1];
if(i%4==1 && record[i]==0)flag[i]=flag[i-1]+1;
else
flag[i]=flag[i-1];
}
while(1)
{
scanf("%d %d",&L,&U);
if(L==-1 && U==-1)exit(0);
if(L<0 && U<0)
{
printf("%d %d 0 0\n",L,U);
continue;
}
sum1=0;
sum2=0;
k=L;
if(k<0)k=0;
sum1=sum[U]-sum[k-1];
sum2=flag[U]-flag[k-1];
if(k<=2 && U>=2)sum2++;
printf("%d %d %d %d\n",L,U,sum1,sum2);
}
return 0;
}