Given an array arr[] consisting of N positive integers, the task is to find an integer greater than 1 which is coprime with all the given array elements.
Examples:
Input: arr[ ] = {10,13,17,19}
Output: 23
Explanation:
The GCD of 23 with every array element is 1. Therefore, 23 is coprime with all the given array elements.Input: arr[] = {13, 17, 23, 24, 50}
Output: 53
Explanation:
The GCD of 53 with every array element is 1. Therefore, 53 is coprime with all the given array elements.
Approach: The idea is to use the fact that a prime number greater than the maximum array element will be coprime with all the given array elements. Therefore, simply find the prime number greater than the largest element present in the array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find an element which// is coprime with all array elementsint find_X(int arr[], int N){ // Stores maximum array element int R = INT_MIN; for (int i = 0; i < N; i++) R = max(R, arr[i]); // Stores if index of an array is prime or not bool prime[1000001]; for (int i = 0; i < 1000001; i++) prime[i] = true; int p = 2; while (p * p <= 1000002) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < 1000001; i += p) { prime[i] = false; } } // Increment p by 1 p = p + 1; } prime[0] = false; prime[1] = false; // Traverse the range [R, 10000000 + 1] for (int i = R; i < 1000001; i++) { // If i is greater than R and prime if (i > R and prime[i] == true) { // Return i return i; } } // Dummy value to omit return error return -1;}// Driven Programint main(){ // Given array int arr[] = { 10, 13, 17, 19 }; // stores the length of array int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << find_X(arr, N); return 0;}// This code is contributed by Kingash. |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to find an element which // is coprime with all array elements static int find_X(int arr[]) { // Stores maximum array element int R = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) R = Math.max(R, arr[i]); // Stores if index of an array is prime or not boolean prime[] = new boolean[1000001]; Arrays.fill(prime, true); int p = 2; while (p * p <= 1000002) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < 1000001; i += p) { prime[i] = false; } } // Increment p by 1 p = p + 1; } prime[0] = false; prime[1] = false; // Traverse the range [R, 10000000 + 1] for (int i = R; i < 1000001; i++) { // If i is greater than R and prime if (i > R && prime[i] == true) { // Return i return i; } } // Dummy value to omit return error return -1; } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 10, 13, 17, 19 }; // Function call System.out.println(find_X(arr)); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approachimport math# Function to find an element which# is coprime with all array elementsdef find_X(arr): # Stores maximum array element R = max(arr) # Stores if index of an array is prime or not prime = [True for i in range(0, 1000001)] p = 2 while (p * p <= 1000002): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * 2, 1000001, p): prime[i] = False # Increment p by 1 p = p + 1 prime[0] = False prime[1] = False # Traverse the range [R, 10000000 + 1] for i in range(R, 1000001): # If i is greater than R and prime if i > R and prime[i] == True: # Return i return i# Driver Codearr = [10, 13, 17, 19]print(find_X(arr)) |
C#
// C# program for the above approachusing System;class GFG{ // Function to find an element which// is coprime with all array elementsstatic int find_X(int[] arr){ // Stores maximum array element int R = Int32.MinValue; for(int i = 0; i < arr.Length; i++) R = Math.Max(R, arr[i]); // Stores if index of an array is prime or not bool[] prime = new bool[1000001]; for(int i = 0; i < 1000001; i++) { prime[i] = true; } int p = 2; while (p * p <= 1000002) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < 1000001; i += p) { prime[i] = false; } } // Increment p by 1 p = p + 1; } prime[0] = false; prime[1] = false; // Traverse the range [R, 10000000 + 1] for(int i = R; i < 1000001; i++) { // If i is greater than R and prime if (i > R && prime[i] == true) { // Return i return i; } } // Dummy value to omit return error return -1;}// Driver Codepublic static void Main(String []args){ // Given array int[] arr = { 10, 13, 17, 19 }; // Function call Console.WriteLine(find_X(arr));}}// This code is contributed by souravghosh0416 |
Javascript
<script>// Javascript program for the above approach// Function to find an element which// is coprime with all array elementsfunction find_X(arr){ // Stores maximum array element let R = Number.MIN_VALUE; for(let i = 0; i < arr.length; i++) R = Math.max(R, arr[i]); // Stores if index of an array is prime or not let prime = Array(1000001).fill(true); let p = 2; while (p * p <= 1000002) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for(let i = p * 2; i < 1000001; i += p) { prime[i] = false; } } // Increment p by 1 p = p + 1; } prime[0] = false; prime[1] = false; // Traverse the range [R, 10000000 + 1] for(let i = R; i < 1000001; i++) { // If i is greater than R and prime if (i > R && prime[i] == true) { // Return i return i; } } // Dummy value to omit return error return -1;}// Driver code// Given arraylet arr = [ 10, 13, 17, 19 ];// Function calldocument.write(find_X(arr));// This code is contributed by target_2 </script> |
Output:
23
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
