Check if there exists a prime number which gives Y after being repeatedly subtracted from X

0 0 3 minutes read

Given two integers X and Y where X > Y, the task is to check if there exists a prime number P such that if P is repeatedly subtracted from X then it gives Y.

Examples:

Input: X = 100, Y = 98
Output: Yes
(100 – (2 * 1) = 98)
Input: X = 45, Y = 31
Output: Yes
(45 – (7 * 2)) = 31

Naive approach: Run a loop for every integer starting from 2 to x. If a current number is a prime number, and it meets the criteria given in the question, then it is the required number.
Efficient approach: Notice that for a valid prime p, x – k * p = y or x – y = k * p. Suppose, p = 2 then (x – y) = 2, 4, 6, … (all even numbers). This means if (x – y) is even then the answer is always true. If (x – y) is an odd number other than 1, it will always have a prime factor. Either it itself is prime or it is a product of a smaller prime and some other integers. So the answer is True for all odd numbers other than 1.
What if (x – y) = 1, it is neither a prime nor composite. So this is the only case where the answer is false.

Below is the implementation of the approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if any
// prime number satisfies
// the given conditions
bool isPossible(int x, int y)
{
 
    // No such prime exists
    if ((x - y) == 1)
        return false;
 
    return true;
}
 
// Driver code
int main()
{
    int x = 100, y = 98;
 
    if (isPossible(x, y))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function that returns true if any
// prime number satisfies
// the given conditions
static boolean isPossible(int x, int y)
{
 
    // No such prime exists
    if ((x - y) == 1)
        return false;
 
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int x = 100, y = 98;
 
    if (isPossible(x, y))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the approach
 
# Function that returns true if any
# prime number satisfies
# the given conditions
def isPossible(x, y):
 
    # No such prime exists
    if ((x - y) == 1):
        return False
 
    return True
 
# Driver code
x = 100
y = 98
 
if (isPossible(x, y)):
    print("Yes")
else:
    print("No")
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function that returns true if any
// prime number satisfies
// the given conditions
static bool isPossible(int x, int y)
{
 
    // No such prime exists
    if ((x - y) == 1)
        return false;
 
    return true;
}
 
// Driver code
public static void Main(String[] args)
{
    int x = 100, y = 98;
 
    if (isPossible(x, y))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript implementation of the approach
 
    // Function that returns true if any
    // prime number satisfies
    // the given conditions
    function isPossible(x , y) {
 
        // No such prime exists
        if ((x - y) == 1)
            return false;
 
        return true;
    }
 
    // Driver code
     
        var x = 100, y = 98;
 
        if (isPossible(x, y))
            document.write("Yes");
        else
            document.write("No");
 
// This code contributed by umadevi9616
</script>

Output:

Yes

Time Complexity: O(1)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!