El número más pequeño que no es coprimo con ningún elemento de una array

Dada una array arr[] de tamaño N , la tarea es encontrar el número más pequeño que no sea coprimo con ningún elemento de la array dada.

Ejemplos: 

Entrada: arr[] = {3, 4, 6, 7, 8, 9, 10}
Salida: 42
Explicación: La factorización prima de los elementos de la array es: 
3 = 3
4 = 2 * 2
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
Considerando factores primos {2, 3, 7} para obtener el número X (= 2 * 3 * 7 = 42), que no es coprimo con cualquier otro elemento de la array.

Entrada: arr[] = {4, 3}
Salida: 6
Explicación: La descomposición en factores primos de los elementos de un arreglo es: 
4 = 2 * 2
3 = 3
Considerando los factores primos {2, 3} para obtener el número X (= 2 * 3 = 6), que no es coprimo con ningún otro elemento del arreglo.

Enfoque: la idea se basa en la observación de que el número requerido, digamos X, no debe ser coprimo con ningún elemento de array arr[i] . Debe existir algún factor común, d ≥ 2 para cada elemento del arreglo arr[i] que divide tanto a arr[i] como a X. El mínimo d posible es un número primo . Por lo tanto, la idea es considerar el conjunto de números primos de modo que su producto no sea coprimo con todos los elementos del arreglo y encontrar el número mínimo posible. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , como INT_MAX para almacenar el resultado requerido.
• Inicialice una array, primos[] para almacenar los números primos .
• Genere todos los subconjuntos de esta array y, para cada subconjunto, almacene su producto en una variable, digamos P. Compruebe si no es coprimo con ninguno de los elementos de la array . Si es cierto, actualice el valor de ans .
• De lo contrario, pase al siguiente subconjunto.
• Después de completar los pasos anteriores, imprima el valor de ans como resultado. 

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX 50
 
// Function check if a
// number is prime or not
bool isPrime(ll n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check if n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    // Check for every 6th number. The above
    // checking allows to skip middle 5 numbers
    for (ll i = 5; i * i <= n; i = i + 6)
 
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to store primes in an array
void findPrime(vector<ll>& primes)
{
    for (ll i = 2; i <= MAX; i++) {
        if (isPrime(i))
            primes.push_back(i);
    }
}
 
// Function to calculate
// GCD of two numbers
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to find the smallest
// number which is not coprime with
// any element of the array arr[]
void findMinimumNumber(ll arr[], ll N)
{
    // Store the prime numbers
    vector<ll> primes;
 
    // Function call to fill
    // the prime numbers
    findPrime(primes);
 
    // Stores the answer
    ll ans = INT_MAX;
 
    ll n = primes.size();
 
    // Generate all non-empty
    // subsets of the primes[] array
    for (ll i = 1; i < (1 << n); i++) {
 
        // Stores product of the primes
        ll temp = 1;
        for (ll j = 0; j < n; j++) {
            if (i & (1 << j)) {
                temp *= primes[j];
            }
        }
 
        // Checks if temp is coprime
        // with the array or not
        bool check = true;
 
        // Check if the product temp is
        // not coprime with the whole array
        for (ll k = 0; k < N; k++) {
            if (gcd(temp, arr[k]) == 1) {
                check = false;
                break;
            }
        }
 
        // If the product is not
        // co-prime with the array
        if (check)
            ans = min(ans, temp);
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given array
    ll arr[] = { 3, 4, 6, 7, 8, 9, 10 };
 
    // Stores the size of the array
    ll N = sizeof(arr) / sizeof(arr[0]);
 
    findMinimumNumber(arr, N);
 
    return 0;
}

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

# Python 3 program for the above approach
MAX = 50
 
import sys
from math import sqrt,gcd
 
# Function check if a
# number is prime or not
def isPrime(n):
   
    # Corner cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True
 
    # Check if n is divisible by 2 or 3
    if (n % 2 == 0 or n % 3 == 0):
        return False
 
    # Check for every 6th number. The above
    # checking allows to skip middle 5 numbers
    for i in range(5,int(sqrt(n))+1,6):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
 
    return True
 
# Function to store primes in an array
def findPrime(primes):
    global MAX
    for i in range(2, MAX + 1, 1):
        if(isPrime(i)):
            primes.append(i)
 
# Function to find the smallest
# number which is not coprime with
# any element of the array arr[]
def findMinimumNumber(arr, N):
   
    # Store the prime numbers
    primes = []
 
    # Function call to fill
    # the prime numbers
    findPrime(primes)
 
    # Stores the answer
    ans = sys.maxsize
    n = len(primes)
 
    # Generate all non-empty
    # subsets of the primes[] array
    for i in range(1, (1 << n), 1):
       
        # Stores product of the primes
        temp = 1
        for j in range(n):
            if (i & (1 << j)):
                temp *= primes[j]
 
        # Checks if temp is coprime
        # with the array or not
        check = True
 
        # Check if the product temp is
        # not coprime with the whole array
        for k in range(N):
            if (gcd(temp, arr[k]) == 1):
                check = False
                break
 
        # If the product is not
        # co-prime with the array
        if (check):
            ans = min(ans, temp)
 
    # Print the answer
    print(ans)
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr =  [3, 4, 6, 7, 8, 9, 10]
     
    # Stores the size of the array
    N = len(arr)
    findMinimumNumber(arr, N)
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static long MAX = 50;
 
// Function check if a
// number is prime or not
static bool isPrime(long n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check if n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    // Check for every 6th number. The above
    // checking allows to skip middle 5 numbers
    for(long i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to store primes in an array
static void findPrime(List<long> primes)
{
    for(long i = 2; i <= MAX; i++)
    {
        if (isPrime(i))
            primes.Add(i);
    }
}
 
// Function to calculate
// GCD of two numbers
static long gcd(long a, long b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to find the smallest
// number which is not coprime with
// any element of the array arr[]
static void findMinimumNumber(long []arr, long N)
{
 
    List<long> primes = new List<long>();
     
    // Function call to fill
    // the prime numbers
    findPrime(primes);
 
    // Stores the answer
    long ans = 2147483647;
 
    int n = primes.Count;
 
    // Generate all non-empty
    // subsets of the primes[] array
    for(int i = 1; i < (1 << n); i++)
    {
         
        // Stores product of the primes
        long temp = 1;
        for(int j = 0; j < n; j++)
        {
            if ((i & (1 << j)) > 0)
            {
                temp *= primes[j];
            }
        }
 
        // Checks if temp is coprime
        // with the array or not
        bool check = true;
 
        // Check if the product temp is
        // not coprime with the whole array
        for(long k = 0; k < N; k++)
        {
            if (gcd(temp, arr[k]) == 1)
            {
                check = false;
                break;
            }
        }
 
        // If the product is not
        // co-prime with the array
        if (check == true)
            ans = Math.Min(ans, temp);
    }
 
    // Prlong the answer
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
     
    // Given array
    long []arr = { 3, 4, 6, 7, 8, 9, 10 };
     
    // Stores the size of the array
    long N = arr.Length;
     
    findMinimumNumber(arr, N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
 
// JavaScript program for the above approach
 
 
let MAX = 50
 
let primes = [];
 
// Function check if a
// number is prime or not
function isPrime(n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check if n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    // Check for every 6th number. The above
    // checking allows to skip middle 5 numbers
    for (let i = 5; i * i <= n; i = i + 6)
 
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to store primes in an array
function findPrime()
{
    for (let i = 2; i <= MAX; i++) {
        if (isPrime(i))
            primes.push(i);
    }
}
 
// Function to calculate
// GCD of two numbers
function gcd(a, b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
// Function to find the smallest
// number which is not coprime with
// any element of the array arr[]
function findMinimumNumber(arr, N)
{
    // Store the prime numbers
 
    // Function call to fill
    // the prime numbers
    findPrime();
 
    // Stores the answer
    let ans = Number.MAX_SAFE_INTEGER;
 
    let n = primes.length;
 
    // Generate all non-empty
    // subsets of the primes[] array
    for (let i = 1; i < (1 << n); i++) {
 
        // Stores product of the primes
        let temp = 1;
        for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
                temp *= primes[j];
            }
        }
 
        // Checks if temp is coprime
        // with the array or not
        let check = true;
 
        // Check if the product temp is
        // not coprime with the whole array
        for (let k = 0; k < N; k++) {
            if (gcd(temp, arr[k]) == 1) {
                check = false;
                break;
            }
        }
 
        // If the product is not
        // co-prime with the array
        if (check)
            ans = Math.min(ans, temp);
    }
 
    // Print the answer
    document.write(ans);
}
 
// Driver Code
// Given array
let arr = [ 3, 4, 6, 7, 8, 9, 10 ];
 
// Stores the size of the array
let N = arr.length;
 
findMinimumNumber(arr, N);
 
</script>

42

Complejidad de tiempo: O(2 ^M *N*log(X)), donde M es el tamaño de la array primos[] y X es el elemento más pequeño de la array arr[]
Espacio auxiliar: O(M)