本文主要是介绍XTU 1237 Prime Twins，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Prime Twins | ||
| [ Submit Code ] [ Top 20 Runs ] | ||
| Acceteped : 55 | Submit : 248 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
Description | ||
题目描述如果n和n+2都是素数，我们称其为孪生素数，比如3和5，5和7都是孪生素数。 给你一个区间[a,b],请问期间有多少对孪生素数？ 输入第一行是一个整数K(K≤ 10000)，表示样例的个数。 以后每行一个样例，为两个整数，a和b，1≤a≤b≤5000000。 输出每行输出一个样例的结果。 样例输入5 1 3 1 10 1 100 1 1000 1 5000000 样例输出0 2 8 35 32463 | ||
Sample Input | ||
Sample Output | ||
Source | ||
| [ Submit Code ] [ Top 20 Runs ] | ||
思路：跟XTU 1098 素数个数那题有些相似。先将素数打个表，即哪些是素数，将它筛选出来。然后判断它与它前面第二个是不是都是素数，是的话，当前答案就为前一个答案加1，否则就为前一个答案。最后对于每一个输入，直接判断输出即可。因为我是两两判断加1，所以a，b之差不能小于2，小于2的话，都没有两个，肯定是无解的，即0。其他即为1~b的个数减去1~a+1的个数。为什么是a+1呢？因为a+1存的是a-1与a+1是不是都是素数的答案，而a之前是不属于该区间的，故应该将其去掉。// 当初考试的时候就是这里没想清楚，WA到死，现在想想，那个时候真是蠢啊。
AC代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000005;
const int sqrt_maxn = 2240;
bool is_prime[maxn];
int cnt_prime[maxn];
int a, b;void init(){is_prime[0] = is_prime[1] = true;for (int i=2; i<=sqrt_maxn; ++i)if (!is_prime[i])for (int j=i*i; j<maxn; j+=i)is_prime[j] = true;for (int i=3; i<maxn; ++i)cnt_prime[i] = cnt_prime[i-1]+(!is_prime[i]&&!is_prime[i-2]);
}int main(){ios::sync_with_stdio(false);cin.tie(0);init();int T;cin >> T;while (T--){cin >> a >> b;if (b-a >= 2)cout << cnt_prime[b]-cnt_prime[a+1] << endl;elsecout << "0" << endl;}return 0;
}
这篇关于XTU 1237 Prime Twins的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
