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 conditionsbool isPossible(int x, int y){ // No such prime exists if ((x - y) == 1) return false; return true;}// Driver codeint main(){ int x = 100, y = 98; if (isPossible(x, y)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function that returns true if any// prime number satisfies// the given conditionsstatic boolean isPossible(int x, int y){ // No such prime exists if ((x - y) == 1) return false; return true;}// Driver codepublic 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 conditionsdef isPossible(x, y): # No such prime exists if ((x - y) == 1): return False return True# Driver codex = 100y = 98if (isPossible(x, y)): print("Yes")else: print("No")# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{// Function that returns true if any// prime number satisfies// the given conditionsstatic bool isPossible(int x, int y){ // No such prime exists if ((x - y) == 1) return false; return true;}// Driver codepublic 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> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
