openoj的一个小比赛（F题解题报告）poj3978(dp+素数筛选）

http://openoj.awaysoft.com:8080/judge/contest/view.action?cid=47#problem/F

一个素数帅选法的题目，才开始直接就套模板结构tle应为被题目中的As many as 1000 lines, 给坑了总的时间消耗是1000*10^5.。这样暴力枚举的话肯定会超时，当时就急了，一下把10^5以内的素数都搜出来了，打表水过。。然后为了问日华，原来在素数帅选完了以后再用dp处理一下就好了。。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int max_s = 100007;
int ip[max_s],dp[max_s];
void init()
{
    int i,j;
    ip[0]=ip[1]=1;
    for(i=2;i*i<max_s;i++)
    {
        if(!ip[i])
        {
            for(j=2*i;j<max_s;j+=i)
            ip[j]=1;
        }
    }
    dp[1]=0;dp[2]=1;
    for(i=3;i<max_s;i++)
    {
        if(!ip[i])
        dp[i]=dp[i-1]+1;
        else
        dp[i]=dp[i-1];
    }
}
int main()
{
    int a,b;
    init();
    while(~scanf("%d%d",&a,&b))
    {
        if(a==-1&&b==-1)
        break;
        if(a==b)
        printf("%d\n",dp[a]-dp[a-1]);
        else
        printf("%d\n",dp[b]-dp[a-1]);
    }
    return 0;
}