Prime Sum PRIMESM Codechef Solution

Prime Sum PRIMESM Codechef Solution

by

Table of 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:

Leave a Comment

2 × one =