素数朋友 prime friend

一时失言乱红尘 2024-02-18 22:40 17阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> <h2>Prime Friend</h2> Time Limit: 4000/2000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4659&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 952 &nbsp; 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. &nbsp; &nbsp; 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 &lt;= T &lt;= 1000 2. 1 &lt;= A, B &lt;= 150 &nbsp; &nbsp; 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. &nbsp; &nbsp; Sample Input <pre>&nbsp;</pre> 2 2 4 3 6 &nbsp; &nbsp; Sample Output <pre>&nbsp;</pre> Case 1: 1 Case 2: -1 &nbsp; &nbsp; Author iSea@WHU &nbsp; &nbsp; Source <a href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=The+6th+Central+China+Invitational+Programming+Contest+and+9th+Wuhan+University+Programming+Contest+Final&amp;source=1&amp;searchmode=source" rel="nofollow">The 6th Central China Invitational Programming Contest and 9th Wuhan University Programming Contest Final </a> &nbsp; &nbsp; Recommend &nbsp; #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;string.h&gt; using namespace std; #define N 21000000 bool &nbsp;a[N+5]; long long b[N+1]; int main() { &nbsp;&nbsp; &nbsp;int T,i,j,k; &nbsp;&nbsp; &nbsp;long long A,B,e=1,t; &nbsp;&nbsp; &nbsp;memset(a,true,sizeof(a)); &nbsp;&nbsp; &nbsp;a[0]=false; &nbsp;&nbsp; &nbsp;a[1]=false; &nbsp;&nbsp; &nbsp;for(i=2;i&lt;N;i++) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(a[i]==true) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(j=i*2;j&lt;N;j+=i) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;a[j]=false; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;b[e++]=i; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;k=1; &nbsp;&nbsp; &nbsp;scanf("%d",&amp;T); &nbsp;&nbsp; &nbsp;while(T--) &nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t=-1; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;scanf("%lld%lld",&amp;A,&amp;B); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(A&gt;B) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;swap(A,B); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(i=1;i&lt;e;i++) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(b[i]&gt;=A&amp;&amp;b[i+1]&gt;=B&amp;&amp;(b[i]-A==b[1+i]-B)) &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;t=b[i]-A; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;break; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;cout&lt;&lt;"Case "&lt;&lt;k++&lt;&lt;": "&lt;&lt;t&lt;&lt;endl; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;return 0; } &nbsp; &nbsp; &nbsp; </td> 
 </tr> 
 </tbody> 
</table>