hdu 3823(素数)

心已赠人 2022-05-31 04:58 113阅读 0赞

问题描述:

Besides the ordinary Boy Friend and Girl Friend, here we define a more academic kind of friend: Prime Friend. We call a nonnegative integer A is the integer B’s Prime Friend when the sum of A and B is a prime.   
So an integer has many prime friends, for example, 1 has infinite prime friends: 1, 2, 4, 6, 10 and so on. This problem is very simple, given two integers A and B, find the minimum common prime friend which will make them not only become primes but also prime neighbor. We say C and D is prime neighbor only when both of them are primes and integer(s) between them is/are not.

Input

The first line contains a single integer T, indicating the number of test cases.   
Each test case only contains two integers A and B.   
  
Technical Specification   
  
1. 1 <= T <= 1000   
2. 1 <= A, B <= 150

Output

For each test case, output the case number first, then the minimum common prime friend of A and B, if not such number exists, output -1.

Sample Input

2
    2 4
    3 6

Sample Output

Case 1: 1
    Case 2: -1

题目题意:给我们俩个数，问我们能不能找到一个数使得a+c与b+c是质数且为相邻质数

题目分析:因为b+c-(a+c)的差值不变，所以我们把相邻的素数的差值保存起来，只需要查找答案即可

G++提交MLE了，C++过了

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #define ll long long
    using namespace std;
    
    const int inf=2*1e7;
    const int maxn=155;
    vector<int> vec[maxn];
    int prime[inf],cnt;
    bool vis[inf];
    
    void get_prime()
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<inf;i++) {
            if (vis[i]) {
                prime[cnt++]=i;
            }
            for (int j=0;j<cnt&&(ll) (i*prime[j])<inf;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    int main()
    {
        int t,icase=1;
        get_prime();
        for (int i=1;i<cnt;i++) {
            if (prime[i]-prime[i-1]<=150) vec[prime[i]-prime[i-1]].push_back(prime[i-1]);
        }
        scanf("%d",&t);
        while (t--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if (l>r) swap(l,r);
            bool flag=false;
            for (int i=0;i<vec[r-l].size();i++) {
                if (vec[r-l][i]>=l) {
                    printf("Case %d: %d\n",icase++,vec[r-l][i]-l);
                    flag=true;
                    break;
                }
            }
            if (!flag) {
                printf("Case %d: %d\n",icase++,-1);
            }
        }
        return 0;
    }