UVA - 1404 Prime k-tuple【筛素数】

缺乏、安全感 2023-07-04 14:14 39阅读 0赞

**discription**  
\{p1, . . . , pk : p1 < p2 < . . . < pk\} is called a prime k-tuple of distance s if p1, p2, . . . , pk are consecutive  
prime numbers and pk − p1 = s. For example, with k = 4, s = 8, \{11, 13, 17, 19\} is a prime 4-tuple of  
distance 8.  
Given an interval \[a, b\], k, and s, your task is to write a program to find the number of prime  
k-tuples of distance s in the interval \[a, b\].

**Input**  
The input file consists of several data sets. The first line of the input file contains the number of data  
sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.  
For each data set, there is only one line containing 4 numbers, a, b, k and s (a, b < 2 ∗ 109, k < 10,s < 40).

**Output**  
For each test case, write in one line the numbers of prime k-tuples of distance s.

**Sample Input**  
1  
100 200 4 8

**Sample Output**  
2

**题意**  
如果有k个相邻的素数，满足pk-p1=s,称这些素数组成一个距离为s的素数k元组，输出区间\[a, b\]内距离为s的k元组

**思路**  
先筛出1e5以内的素数，然后再进行判断。

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 100005;
    
    int prime[maxn], vis[maxn], cnt;
    
    void init()
    { 
        memset(vis, 0, sizeof(0));
        vis[1] = vis[0] = 1;
        cnt = 0;
        for (ll i = 2; i < maxn; i++)
            if (!vis[i])
            { 
                prime[cnt++] = i;
                for (ll j = i*i; j < maxn; j += i)
                    vis[j] = 1;
            }
    }
    
    int check(int n)
    { 
        if (n < maxn)
            return vis[n] == 0;
        for (int i = 0; i < cnt && prime[i]*prime[i] <= n; i++)
            if (n % prime[i] == 0)
                return 0;
        return 1;
    }
    
    
    int main()
    { 
        init();
        int t, a, b, k, s;
        scanf("%d", &t);
        while (t--)
        { 
            scanf("%d%d%d%d", &a, &b, &k, &s);
            int ans = 0;
            vector<int> v;
            for (int i = a; i <= b; i++)
                if (check(i))
                    v.push_back(i);
            for (int i=0; i+k-1<v.size();i++)
                if (v[i+k-1]-v[i]==s)
                    ans++;
            printf("%d\n", ans);
        }
        return 0;
    }