Smallest number which is not coprime with any element of an array | Java program for the above approach ; Function check if a number is prime or not ; Corner cases ; Check if n is divisible by 2 or 3 ; Check for every 6 th number . The above checking allows to skip middle 5 numbers ; Function to store primes in an array ; Function to calculate GCD of two numbers ; Function to find the smallest number which is not coprime with any element of the array arr [ ] ; Function call to fill the prime numbers ; Stores the answer ; Generate all non - empty subsets of the primes [ ] array ; Stores product of the primes ; Checks if temp is coprime with the array or not ; Check if the product temp is not coprime with the whole array ; If the product is not co - prime with the array ; Prlong the answer ; Driver code ; Given array ; Stores the size of the array
import java . util . * ; class GFG { static long MAX = 50 ; static boolean isPrime ( long n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return true ; if ( n % 2 == 0 n % 3 == 0 ) return false ; for ( long i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return false ; return true ; } static void findPrime ( ArrayList < Long > primes ) { for ( long i = 2 ; i <= MAX ; i ++ ) { if ( isPrime ( i ) ) primes . add ( i ) ; } } static long gcd ( long a , long b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ) ; } static void findMinimumNumber ( long [ ] arr , long N ) { ArrayList < Long > primes = new ArrayList < Long > ( ) ; findPrime ( primes ) ; long ans = 2147483647 ; int n = primes . size ( ) ; for ( int i = 1 ; i < ( 1 << n ) ; i ++ ) { long temp = 1 ; for ( int j = 0 ; j < n ; j ++ ) { if ( ( i & ( 1 << j ) ) > 0 ) { temp *= primes . get ( j ) ; } } boolean check = true ; for ( long k = 0 ; k < N ; k ++ ) { if ( gcd ( temp , arr [ ( int ) k ] ) == 1l ) { check = false ; break ; } } if ( check == true ) ans = Math . min ( ans , temp ) ; } System . out . print ( ans ) ; } public static void main ( String [ ] args ) { long [ ] arr = { 3 , 4 , 6 , 7 , 8 , 9 , 10 } ; long N = arr . length ; findMinimumNumber ( arr , N ) ; } }