本文主要是介绍PTA-----＞幸运数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，题目：
Rain Sure同学定义了幸运数字——如果一个正整数n是幸运数字，那么当且仅当n和(n+1)/2都是素数。
现在给定q次查询：
第i次询问给定两个正整数li,ri，请你求出在区间[li,ri]中有多少个数字是幸运数字。
输入格式
第一行一个正整数q。
后面q行，每行两个正整数li,ri
1≤q≤105
1≤li≤ri≤105
输出格式
对于每次询问，输出答案，每个答案单独占据一行。
测试样例一
1
3 7
2
测试样例二
4
13 13
7 11
7 11
2017 2017
1
0
0
1
测试样例三
6
1 53
13 91
37 55
19 51
73 91
13 49
4
4
1
1
1
2二，思路：
将1-1e5所有幸运数预处理出来，利用前缀和来维护每个区间的幸运数数量。
三，代码：
#include <iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<stack>
#include<queue>
#include<map>
using namespace std;const int N=1e5+10,M=1e9+7;typedef long long ll;
typedef pair<int,int> pii;bool isprime(int x){for(int i=2;i<=x/i;i++){if(x%i==0) return false;}return true;
}int st[N];
int pre[N];void Solved() {int q;cin>>q;for(int i=2;i<=1e5;i++){if(isprime(i)) st[i]=1;}//预处理for(int i=2;i<=1e5;i++){if(st[(i+1)/2]==1&&st[i]==1){pre[i]=1;}}//前缀和for(int i=2;i<=1e5;i++){pre[i]+=pre[i-1];}while(q--){int l,r;cin>>l>>r;//查询区间cout<<pre[r]-pre[l-1]<<endl;}
}int main()
{int t;//cin>>t;t=1;while(t--) {Solved();}return 0;
}
这篇关于PTA-----＞幸运数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
