首页 > 代码库 > uva 1404 - Prime k-tuple(数论)
uva 1404 - Prime k-tuple(数论)
题目链接:uva 1404 1404 - Prime k-tuple
题目大意:如果k个相邻的素数p1,p2,…,pk,满足pk?p1=s,称这些素数组成一个距离为s的素数k元组,给定区间a,b,求有多少个距离s的k元组。
解题思路:筛选素数法,先预处理出[1, sqrt(inf)]的素数表,然后对给定区间[a,b]根据预处理出的素数表筛选出素数即可。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int sqrt_inf = 46340;
const int maxn = 2 * 1e9;
int np, pri[sqrt_inf];
bool vis[maxn+5];
vector<int> vec;
void prime_table (int n) {
np = 0;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = i * i; j <= n; j += i)
vis[j] = 1;
}
}
int solve () {
int ret = 0;
int a, b, s, k;
vec.clear();
memset(vis, 0, sizeof(vis));
scanf("%d%d%d%d", &a, &b, &k, &s);
for (int i = 0; i < np && pri[i] * pri[i] <= b; i++) {
int u = pri[i], d = (u - a % u) % u;
if (u == a + d)
d += u;
while (d <= b - a) {
vis[d] = 1;
d += u;
}
}
for (int i = 0; i <= b-a; i++) {
if (vis[i] == 0 && a + i > 1)
vec.push_back(a+i);
}
for (int i = 0; i + k - 1 < vec.size(); i++) {
if (vec[i+k-1] - vec[i] == s)
ret++;
}
return ret;
}
int main () {
prime_table(sqrt_inf);
int cas;
scanf("%d", &cas);
while (cas--) {
printf("%d\n", solve());
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。