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;elsedp[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]);elseprintf("%d\n",dp[b]-dp[a-1]);}return 0;
}

　　

轉載于:https://www.cnblogs.com/E-star/archive/2011/11/27/2264779.html

總結

以上是生活随笔為你收集整理的openoj的一个小比赛（F题解题报告）poj3978(dp+素数筛选）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。