Given two positive integers L and R, the task is to find an integer X greater than 1 such that X is co-prime with all the integers from the range [L, R].
Examples:
Input: L = 16, R = 17
Output: 19
Explanation: Only number which is co-prime with all the integers from the range [16, 17] is 9.Input: L = 973360, R = 973432
Output: 973439
Approach: The simplest approach to solve the given problem is to find a prime number greater than R, because this integer does not divide any integer in the range of [L, R]. Therefore, the idea is to iterate from the value (R + 1) and if there exists any integer which is prime, then print that integer and break out of the loop.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether the // given number N is prime or not bool isPrime( int N) { // Base Case if (N == 1) return false ; for ( int i = 2; i * i <= N; i++) { // If N has more than one // factor, then return false if (N % i == 0) return false ; } // Otherwise, return true return true ; } // Function to find X which is co-prime // with the integers from the range [L, R] int findCoPrime( int L, int R) { // Store the resultant number int coPrime; // Check for prime integers // greater than R for ( int i = R + 1;; i++) { // If the current number is // prime, then update coPrime // and break out of loop if (isPrime(i)) { coPrime = i; break ; } } // Print the resultant number return coPrime; } // Driver Code int main() { int L = 16, R = 17; cout << findCoPrime(L, R); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to check whether the // given number N is prime or not static boolean isPrime( int N) { // Base Case if (N == 1 ) return false ; for ( int i = 2 ; i * i <= N; i++) { // If N has more than one // factor, then return false if (N % i == 0 ) return false ; } // Otherwise, return true return true ; } // Function to find X which is co-prime // with the integers from the range [L, R] static int findCoPrime( int L, int R) { // Store the resultant number int coPrime; // Check for prime integers // greater than R for ( int i = R + 1 ;; i++) { // If the current number is // prime, then update coPrime // and break out of loop if (isPrime(i)) { coPrime = i; break ; } } // Print the resultant number return coPrime; } // Driver Code public static void main(String[] args) { int L = 16 , R = 17 ; System.out.println(findCoPrime(L, R)); } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach # Function to check whether the # given number N is prime or not def isPrime(N): # Base Case if (N = = 1 ): return False for i in range ( 2 , N + 1 ): if i * i > N: break # If N has more than one # factor, then return false if (N % i = = 0 ): return False # Otherwise, return true return True # Function to find X which is co-prime # with the integers from the range [L, R] def findCoPrime(L, R): # Store the resultant number coPrime, i = 0 , R + 1 # Check for prime integers # greater than R while True : # If the current number is # prime, then update coPrime # and break out of loop if (isPrime(i)): coPrime = i break i + = 1 # Print the resultant number return coPrime # Driver Code if __name__ = = '__main__' : L,R = 16 , 17 print (findCoPrime(L, R)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG{ // Function to check whether the // given number N is prime or not static bool isPrime( int N) { // Base Case if (N == 1) return false ; for ( int i = 2; i * i <= N; i++) { // If N has more than one // factor, then return false if (N % i == 0) return false ; } // Otherwise, return true return true ; } // Function to find X which is co-prime // with the integers from the range [L, R] static int findCoPrime( int L, int R) { // Store the resultant number int coPrime; // Check for prime integers // greater than R for ( int i = R + 1;; i++) { // If the current number is // prime, then update coPrime // and break out of loop if (isPrime(i)) { coPrime = i; break ; } } // Print the resultant number return coPrime; } // Driver Code public static void Main( string [] args) { int L = 16, R = 17; Console.WriteLine(findCoPrime(L, R)); } } // This code is contributed by ukasp |
Javascript
<script> // javascript program for the above approach // Function to check whether the // given number N is prime or not function isPrime(N) { // Base Case if (N == 1) return false ; for ( var i = 2; i * i <= N; i++) { // If N has more than one // factor, then return false if (N % i == 0) return false ; } // Otherwise, return true return true ; } // Function to find X which is co-prime // with the integers from the range [L, R] function findCoPrime(L , R) { // Store the resultant number var coPrime; // Check for prime integers // greater than R for ( var i = R + 1;; i++) { // If the current number is // prime, then update coPrime // and break out of loop if (isPrime(i)) { coPrime = i; break ; } } // Print the resultant number return coPrime; } // Driver Code var L = 16, R = 17; document.write(findCoPrime(L, R)); // This code contributed by Princi Singh </script> |
19
Time Complexity: O(L * R1/2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!