Dada una array arr[] que tiene N enteros, la tarea es encontrar el MCD de todos los números de la array que no son primos. Si todos los números son primos, devuelve -1.
Ejemplos:
Entrada: N = 3, arr[ ] = {2, 3, 5}
Salida: -1
Explicación: Todos los números son primos.
Por lo tanto la respuesta será -1.Entrada: N = 6, arr[ ] = { 2, 4, 6, 12, 3, 5 }
Salida: 2
Explicación: Los números no primos presentes en la array son 4, 6 y 12.
Su GCD es 2.
Enfoque: este problema se puede resolver encontrando los números primos en la array usando la criba de Eratóstenes .
Siga los pasos a continuación para resolver el problema:
- Encuentre todos los números primos en el rango de mínimo de la array y máximo de la array utilizando el tamiz de Eratóstenes .
- Ahora itere a través de la array dada y encuentre los números no primos.
- Toma MCD de todos los números no primos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; vector<int> isPrime(100001, 1); // Function to find the prime numbers void sieve(int n) { // Mark 0 and 1 as non-prime isPrime[0] = 0; isPrime[1] = 0; // Mark all multiples of 2 as // non-prime for (int i = 4; i <= n; i += 2) isPrime[i] = 0; // Mark all non-prime numbers for (int i = 3; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) isPrime[j] = 0; } } } // Find the GCD of the non-prime numbers int nonPrimeGCD(vector<int>& arr, int n) { int i = 0; // Find all non-prime numbers till n // using sieve of Eratosthenes sieve(n); // Find first non - prime number // in the array while (isPrime[arr[i]] and i < n) i++; // If not found return -1 if (i == n) return -1; // Initialize GCD as the first // non prime number int gcd = arr[i]; // Take gcd of all non-prime numbers for (int j = i + 1; j < n; j++) { if (!isPrime[arr[j]]) gcd = __gcd(gcd, arr[j]); } return gcd; } // Driver code int main() { int N = 6; vector<int> arr = { 2, 4, 6, 12, 3, 5 }; // Find non Prime GCD cout << nonPrimeGCD(arr, N); return 0; }
Java
// Java code to implement the approach import java.io.*; class GFG { static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } static int[] isPrime = new int[100001]; // Function to find the prime numbers public static void sieve(int n) { for (int i = 0; i <= n; i++) { isPrime[i] = 1; } // Mark 0 and 1 as non-prime isPrime[0] = 0; isPrime[1] = 0; // Mark all multiples of 2 as // non-prime for (int i = 4; i <= n; i += 2) isPrime[i] = 0; // Mark all non-prime numbers for (int i = 3; i * i <= n; i++) { if (isPrime[i] != 0) { for (int j = i * i; j <= n; j += i) isPrime[j] = 0; } } } // Find the GCD of the non-prime numbers public static int nonPrimeGCD(int arr[], int n) { int i = 0; // Find all non-prime numbers till n // using sieve of Eratosthenes sieve(n); // Find first non - prime number // in the array while (isPrime[arr[i]] != 0 && i < n) i++; // If not found return -1 if (i == n) return -1; // Initialize GCD as the first // non prime number int gg = arr[i]; // Take gcd of all non-prime numbers for (int j = i + 1; j < n; j++) { if (isPrime[arr[j]] == 0) gg = gcd(gg, arr[j]); } return gg; } // Driver Code public static void main(String[] args) { int N = 6; int arr[] = { 2, 4, 6, 12, 3, 5 }; // Find non Prime GCD System.out.print(nonPrimeGCD(arr, N)); } } // This code is contributed by Rohit Pradhan
Python3
# python3 code to implement the approach import math isPrime = [1 for _ in range(1000011)] # Function for __gcd def __gcd(a, b): if b == 0: return a return __gcd(b, a % b) # Function to find the prime numbers def sieve(n): global isPrime # Mark 0 and 1 as non-prime isPrime[0] = 0 isPrime[1] = 0 # Mark all multiples of 2 as # non-prime for i in range(4, n+1, 2): isPrime[i] = 0 # Mark all non-prime numbers for i in range(3, int(math.sqrt(n)) + 1): if (isPrime[i]): for j in range(i*i, n+1, i): isPrime[j] = 0 # Find the GCD of the non-prime numbers def nonPrimeGCD(arr, n): i = 0 # Find all non-prime numbers till n # using sieve of Eratosthenes sieve(n) # Find first non - prime number # in the array while (isPrime[arr[i]] and i < n): i += 1 # If not found return -1 if (i == n): return -1 # Initialize GCD as the first # non prime number gcd = arr[i] # Take gcd of all non-prime numbers for j in range(i+1, n): if (not isPrime[arr[j]]): gcd = __gcd(gcd, arr[j]) return gcd # Driver code if __name__ == "__main__": N = 6 arr = [2, 4, 6, 12, 3, 5] # Find non Prime GCD print(nonPrimeGCD(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program for above approach using System; class GFG { static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } static int[] isPrime = new int[100001]; // Function to find the prime numbers public static void sieve(int n) { for (int i = 0; i <= n; i++) { isPrime[i] = 1; } // Mark 0 and 1 as non-prime isPrime[0] = 0; isPrime[1] = 0; // Mark all multiples of 2 as // non-prime for (int i = 4; i <= n; i += 2) isPrime[i] = 0; // Mark all non-prime numbers for (int i = 3; i * i <= n; i++) { if (isPrime[i] != 0) { for (int j = i * i; j <= n; j += i) isPrime[j] = 0; } } } // Find the GCD of the non-prime numbers public static int nonPrimeGCD(int[] arr, int n) { int i = 0; // Find all non-prime numbers till n // using sieve of Eratosthenes sieve(n); // Find first non - prime number // in the array while (isPrime[arr[i]] != 0 && i < n) i++; // If not found return -1 if (i == n) return -1; // Initialize GCD as the first // non prime number int gg = arr[i]; // Take gcd of all non-prime numbers for (int j = i + 1; j < n; j++) { if (isPrime[arr[j]] == 0) gg = gcd(gg, arr[j]); } return gg; } // Driver Code public static void Main() { int N = 6; int[] arr = { 2, 4, 6, 12, 3, 5 }; // Find non Prime GCD Console.Write(nonPrimeGCD(arr, N)); } } // This code is contributed by code_hunt.
Javascript
<script> // JavaScript code to implement the approach let isPrime = new Array(100001).fill(1) // Function to find the prime numbers function sieve(n) { // Mark 0 and 1 as non-prime isPrime[0] = 0; isPrime[1] = 0; // Mark all multiples of 2 as // non-prime for (let i = 4; i <= n; i += 2) isPrime[i] = 0; // Mark all non-prime numbers for (let i = 3; i * i <= n; i++) { if (isPrime[i]) { for (let j = i * i; j <= n; j += i) isPrime[j] = 0; } } } function GCD(x,y){ if (!y) { return x; } return GCD(y, x % y); } // Find the GCD of the non-prime numbers function nonPrimeGCD(arr,n) { let i = 0; // Find all non-prime numbers till n // using sieve of Eratosthenes sieve(n); // Find first non - prime number // in the array while (isPrime[arr[i]] && i < n) i++; // If not found return -1 if (i == n) return -1; // Initialize GCD as the first // non prime number let gcd = arr[i]; // Take gcd of all non-prime numbers for (let j = i + 1; j < n; j++) { if (!isPrime[arr[j]]) gcd = GCD(gcd, arr[j]); } return gcd; } // Driver code let N = 6 let arr = [ 2, 4, 6, 12, 3, 5 ] // Find non Prime GCD document.write(nonPrimeGCD(arr, N)) // This code is contributed by shinjanpatra </script>
2
Complejidad de tiempo: O(N * log(log( N )))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA