传送门：http://www.cnblogs.com/huoxiayu/p/4681015.html

Problem Description 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 <= T <= 10001 <= 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

/*题意：给出两个整数ab 使a+x b+x均为素数 且ab之间没有素数 求最小的符合条件的x*/ #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> using namespace std; typedef long long ll; const int N = 20000001; const int M = 1500000; const int K = 150; const int L = 200000; bool visit[N]; int prime[M]; int ss[K][L]; int pm[K]; int pn; void better_get_prime() { pn = 0; memset( visit, 0, sizeof(visit) ); visit[0] = visit[1] = 1; for ( int i = 2; i < N; i++ ) { if ( !visit[i] ) prime[pn++] = i; for ( int j = 0; j < pn && ( ll ) i * prime[j] < N; j++ ) { visit[i * prime[j]] = 1; if ( i % prime[j] == 0 ) break; } } memset( pm, 0, sizeof(pm) ); for ( int i = 0; i < pn - 1; i++ ) { int d = prime[i + 1] - prime[i]; if ( d < K ) { ss[d][pm[d]++] = prime[i]; } } } int main () { better_get_prime(); int t; scanf("%d", &t); for ( int _case = 1; _case <= t; _case++ ) { int x, y; scanf("%d%d", &x, &y); if ( x > y ) swap( x, y ); int d = y - x, ans = -1; for ( int i = 0; i < pm[d]; i++ ) { if ( ss[d][i] >= x ) { ans = ss[d][i] - x; break; } } printf("Case %d: %d\n", _case, ans); } return 0; }