# Prime Sum PRIMESM Codechef Solution

Page Contents

## Prime Sum PRIMESM Codechef Solution

Given two integers A and B.

Let P denote a sequence of N prime numbers such that the sum of the sequence is A.
Let Q denote a sequence of M prime numbers such that the sum of the sequence is B.
Let X denote the maximum absolute difference between Pi and Qj among all valid pairs (i,j) such that (1≤i≤N) and (1≤j≤M). Find the minimum possible value of X over all possible sequences P and Q.

More formally, for all possible sequences P and Q, find the minimum value of max(|Pi−Qj|), where (1≤i≤N) and (1≤j≤M).

Print −1 if any one of the sequences cannot be formed.

Note that, |X| denotes the absolute value of a number X. For example, |−4|=4 and |7|=7.

Input Format
First line will contain T, the number of test cases. Then the test cases follow.
Each test case contains two integers A and B.

Output Format
For each test case, find the minimum possible value of the maximum absolute difference between Pi and Qj for (1≤i≤N) and (1≤j≤M). If any of the sequences can not be formed, print −1 instead.

Constraints
1≤T≤105
1≤A≤1018
1≤B≤1018
Sample Input 1
2
3 6
3 2
Sample Output 1
0
1
Explanation
Test case 1: Let P={3} and Q={3,3}.
The maximum absolute difference is 0. It can be shown that the maximum absolute difference can not be less than 0.

Test case 2: The only possible sequences are P={3} and Q={2}.
The maximum absolute difference is 1. It can be shown that the maximum absolute difference can not be less than 1.

## SOLUTION

Program: Prime Sum PRIMESM Codechef Solution in Python

```def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)

for _ in range(int(input())):
a,b = map(int,input().split(" "))
if a==1 or b==1:
print(-1)
else:
t = gcd(a,b)
if t != 1:
print(0)
else:
print(1)```

Program: Prime Sum PRIMESM Codechef Solution in C++

```#include<bits/stdc++.h>
using namespace std;
#define f for(ll i=0;i<n;i++)
typedef long long ll;
int main(){
ll t;
cin>>t;
while(t--){
ll x,y;
cin>>x>>y;
if(x==1 || y==1)
cout<<-1<<endl;
else if(__gcd(x,y)!=1)
cout<<0<<endl;
else
cout<<1<<endl;
}
}```

Program: Prime Sum PRIMESM Codechef Solution in Java

```import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
static long gcd(long a, long b){
if (b == 0) return a;
return gcd(b, a%b);
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
long a = sc.nextLong();
long b = sc.nextLong();
if (a==1 || b==1){
System.out.println(-1);
}
else if (gcd(a,b)==1){
System.out.println(1);
}
else
System.out.println(0);
}
}
}```

Related: