Smallest number which is not coprime with any element of an array | JavaScript 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 ; Given array ; Stores the size of the array
let MAX = 50 let primes = [ ] ; function isPrime ( n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return true ; if ( n % 2 == 0 n % 3 == 0 ) return false ; for ( let i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return false ; return true ; } function findPrime ( ) { for ( let i = 2 ; i <= MAX ; i ++ ) { if ( isPrime ( i ) ) primes . push ( i ) ; } } function gcd ( a , b ) { if ( b == 0 ) return a ; else return gcd ( b , a % b ) ; } function findMinimumNumber ( arr , N ) { findPrime ( ) ; let ans = Number . MAX_SAFE_INTEGER ; let n = primes . length ; for ( let i = 1 ; i < ( 1 << n ) ; i ++ ) { let temp = 1 ; for ( let j = 0 ; j < n ; j ++ ) { if ( i & ( 1 << j ) ) { temp *= primes [ j ] ; } } let check = true ; for ( let k = 0 ; k < N ; k ++ ) { if ( gcd ( temp , arr [ k ] ) == 1 ) { check = false ; break ; } } if ( check ) ans = Math . min ( ans , temp ) ; } document . write ( ans ) ; } let arr = [ 3 , 4 , 6 , 7 , 8 , 9 , 10 ] ; let N = arr . length ; findMinimumNumber ( arr , N ) ;