Encuentre el MCD de todos los números no primos de Array dado

Posted on by Rudeus Greyrat

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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *