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处理一下就好了。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}
网址：openoj的一个小比赛（F题解题报告）poj3978(dp+素数筛选） https://mxgxt.com/news/view/224538
相关内容
一帧搜索筛选里的短视频KOL粉丝画像筛选是什么意思？中学生对偶像崇拜问题(结题报告)
体育赛事分析报告.pptx
列表、字典、集合中筛选数据
奶粉行业专题研究报告.docx
媒体评选国内影响力最大的10大模特比赛排名#模特大赛报名
3大维度拆解KOL数据 助力品牌方寻找小红书优质KOL
哈市铁岭小学举行《提升小学教师中华优秀传统文化素养途径与方法的研究》课题开题会暨教师素养展示
百度图片搜索明星图片，不能筛选尺寸，只能选择项目和日期，怎么像以前一样可以筛选尺寸啊
KOL背后的筛选逻辑和营销玩法
