Smallest number which is not coprime with any element of an array | C ++ 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 ; Print the answer ; Driver Code ; Given array ; Stores the size of the array
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE #define MAX  50 NEW_LINE bool isPrime ( ll n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return true ; if ( n % 2 == 0 n % 3 == 0 ) return false ; for ( ll i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return false ; return true ; } void findPrime ( vector < ll > & primes ) { for ( ll i = 2 ; i <= MAX ; i ++ ) { if ( isPrime ( i ) ) primes . push_back ( i ) ; } } ll gcd ( ll a , ll b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ) ; } void findMinimumNumber ( ll arr [ ] , ll N ) { vector < ll > primes ; findPrime ( primes ) ; ll ans = INT_MAX ; ll n = primes . size ( ) ; for ( ll i = 1 ; i < ( 1 << n ) ; i ++ ) { ll temp = 1 ; for ( ll j = 0 ; j < n ; j ++ ) { if ( i & ( 1 << j ) ) { temp *= primes [ j ] ; } } bool check = true ; for ( ll k = 0 ; k < N ; k ++ ) { if ( gcd ( temp , arr [ k ] ) == 1 ) { check = false ; break ; } } if ( check ) ans = min ( ans , temp ) ; } cout << ans ; } int main ( ) { ll arr [ ] = { 3 , 4 , 6 , 7 , 8 , 9 , 10 } ; ll N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findMinimumNumber ( arr , N ) ; return 0 ; }