Encuentra números primos en una array 2D (array)

Dada una array 2d mat[][] , la tarea es encontrar e imprimir los números primos junto con su posición (indexación basada en 1) en esta array 2d.

Ejemplos:

Entrada: mat[][] = {{1, 2}, {2, 1}}  

Producción: 

1 2 2

2 1 2

Explicación:  El primer primo está en la posición de la fila 1 y la columna 2 y el valor es 2

El segundo primo está en la posición de la fila 2 y la columna 1 y el valor es 2

Entrada: mat[][] = {{1, 1}, {1, 1}}  

Salida: -1

Explicación:  No hay ningún número primo en esta array 2d

 

Enfoque ingenuo: la idea básica es recorrer la array 2d y, para cada número, verificar si es primo o no. Si es primo, imprime la posición y el valor de cada número primo encontrado.
Complejidad de tiempo: O(NM*sqrt(X)), donde N*M es el tamaño de la array y X es el elemento más grande de la array
Espacio auxiliar: O(1) 

Enfoque eficiente: podemos verificar de manera eficiente si el número es primo o no usando tamiz. Luego, recorra la array 2d y simplemente verifique si el número es primo o no en O (1). 

Siga los pasos a continuación para implementar este enfoque:

  • Encuentre el elemento máximo de la array y guárdelo en una variable maxNum .
  • Ahora encuentre los números primos del 1 al maxNum usando el tamiz de eratóstenes y almacene el resultado en el arreglo prime[] .
  • Ahora recorra la array y para cada número verifique si es primo o no usando la array primo[] .
  • Para cada número primo en la array, imprima su posición (fila, columna) y valor.

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

C++

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 100001
bool prime[MAXN];
 
// Function to find prime numbers using sieve
void SieveOfEratosthenes()
{
    int n = MAXN - 1;
 
    // Create a boolean array
    // "prime[0..n]" and initialize
    // all entries it as true.
    // A value in prime[i] will
    // finally be false if i is
    // Not a prime, else true.
    memset(prime, true, sizeof(prime));
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
            // Update all multiples
            // of p greater than or
            // equal to the square of it
            // numbers which are multiple
            // of p and are less than p^2
            // are already been marked.
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to print the position and
// value of the primes in given matrix
void printPrimes(vector<vector<int> >& arr, int n)
{
    // Traverse the matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
 
            // Check if the element is prime
            // or not in O(1)
            if (prime[arr[i][j]] == true) {
                // Print the position and value
                // if found true
                cout << i + 1 << " " << j + 1 << " "
                     << arr[i][j] << endl;
            }
        }
    }
}
 
// Driver Code
int main()
{
    int N = 2;
    vector<vector<int> > arr;
    vector<int> temp(N, 2);
    temp[0] = 1;
    temp[1] = 2;
    arr.push_back(temp);
    temp[0] = 2;
    temp[1] = 1;
    arr.push_back(temp);
 
    // Precomputing prime numbers using sieve
    SieveOfEratosthenes();
 
    // Find and print prime numbers
    // present in the matrix
    printPrimes(arr, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    static int MAXN = 100001;
    static boolean prime[] = new boolean[MAXN];
 
    // Function to find prime numbers using sieve
    static void SieveOfEratosthenes()
    {
        int n = MAXN - 1;
        Arrays.fill(prime, true);
       
        // Create a boolean array
        // "prime[0..n]" and initialize
        // all entries it as true.
        // A value in prime[i] will
        // finally be false if i is
        // Not a prime, else true.
        prime[0] = false;
        prime[1] = false;
 
        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
                // Update all multiples
                // of p greater than or
                // equal to the square of it
                // numbers which are multiple
                // of p and are less than p^2
                // are already been marked.
                for (int i = p * p; i <= n; i = i + p)
                    prime[i] = false;
            }
        }
    }
 
    // Function to print the position and
    // value of the primes in given matrix
    static void printPrimes(int[][] arr, int n)
    {
        // Traverse the matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
 
                // Check if the element is prime
                // or not in O(1)
                if (prime[arr[i][j]] == true) {
                    // Print the position and value
                    // if found true
                    System.out.print((i + 1));
                    System.out.print(" ");
                    System.out.print(j + 1);
                    System.out.print(" ");
                    System.out.print(arr[i][j]);
                    System.out.println();
                }
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 2;
        int arr[][] = new int[N][N];
 
        arr[0][0] = 1;
        arr[0][1] = 2;
        arr[1][0] = 2;
        arr[1][1] = 1;
 
        // Precomputing prime numbers using sieve
        SieveOfEratosthenes();
 
        // Find and print prime numbers
        // present in the matrix
        printPrimes(arr, N);
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# python code to implement the above approach
import math
MAXN = 100001
prime = [True for _ in range(MAXN)]
 
# Function to find prime numbers using sieve
def SieveOfEratosthenes():
    global prime
 
    n = MAXN - 1
 
    # Create a boolean array
    # "prime[0..n]" and initialize
    # all entries it as true.
    # A value in prime[i] will
    # finally be false if i is
    # Not a prime, else true.
    prime[0] = False
    prime[1] = False
 
    for p in range(2, int(math.sqrt(n)) + 1):
       
                # If prime[p] is not changed,
                # then it is a prime
        if (prime[p] == True):
           
           # Update all multiples
           # of p greater than or
           # equal to the square of it
           # numbers which are multiple
           # of p and are less than p^2
           # are already been marked.
            for i in range(p*p, n+1, p):
                prime[i] = False
 
# Function to print the position and
# value of the primes in given matrix
def printPrimes(arr, n):
 
        # Traverse the matrix
    for i in range(0, n):
        for j in range(0, n):
 
                        # Check if the element is prime
                        # or not in O(1)
            if (prime[arr[i][j]] == True):
               
                # Print the position and value
                # if found true
                print(f"{i + 1} {j + 1} {arr[i][j]}")
 
# Driver Code
if __name__ == "__main__":
 
    N = 2
    arr = []
    temp = [2 for _ in range(N)]
     
    temp[0] = 1
    temp[1] = 2
    arr.append(temp.copy())
    temp[0] = 2
    temp[1] = 1
    arr.append(temp.copy())
 
    # Precomputing prime numbers using sieve
    SieveOfEratosthenes()
 
    # Find and print prime numbers
    # present in the matrix
    printPrimes(arr, N)
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
    static int MAXN = 100001;
    static bool[] prime = new bool[MAXN];
 
    // Function to find prime numbers using sieve
    static void SieveOfEratosthenes()
    {
        int n = MAXN - 1;
        Array.Fill(prime, true);
       
        // Create a boolean array
        // "prime[0..n]" and initialize
        // all entries it as true.
        // A value in prime[i] will
        // finally be false if i is
        // Not a prime, else true.
        prime[0] = false;
        prime[1] = false;
 
        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true) {
                // Update all multiples
                // of p greater than or
                // equal to the square of it
                // numbers which are multiple
                // of p and are less than p^2
                // are already been marked.
                for (int i = p * p; i <= n; i = i + p)
                    prime[i] = false;
            }
        }
    }
 
    // Function to print the position and
    // value of the primes in given matrix
    static void printPrimes(int[,] arr, int n)
    {
        // Traverse the matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
 
                // Check if the element is prime
                // or not in O(1)
                if (prime[arr[i,j]] == true) {
                    // Print the position and value
                    // if found true
                    Console.Write((i + 1));
                    Console.Write(" ");
                    Console.Write(j + 1);
                    Console.Write(" ");
                    Console.Write(arr[i,j]);
                    Console.WriteLine();
                }
            }
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 2;
        int[,] arr = new int[N,N];
 
        arr[0,0] = 1;
        arr[0,1] = 2;
        arr[1,0] = 2;
        arr[1,1] = 1;
 
        // Precomputing prime numbers using sieve
        SieveOfEratosthenes();
 
        // Find and print prime numbers
        // present in the matrix
        printPrimes(arr, N);
    }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
 
       // JavaScript Program to implement
       // the above approach
 
 
       let MAXN = 100001
       let prime = new Array(MAXN).fill(true);
 
       // Function to find prime numbers using sieve
       function SieveOfEratosthenes() {
           let n = MAXN - 1;
 
           // Create a boolean array
           // "prime[0..n]" and initialize
           // all entries it as true.
           // A value in prime[i] will
           // finally be false if i is
           // Not a prime, else true.
 
           prime[0] = false;
           prime[1] = false;
 
           for (let p = 2; p * p <= n; p++) {
               // If prime[p] is not changed,
               // then it is a prime
               if (prime[p] == true) {
                   // Update all multiples
                   // of p greater than or
                   // equal to the square of it
                   // numbers which are multiple
                   // of p and are less than p^2
                   // are already been marked.
                   for (let i = p * p; i <= n; i = i + p)
                       prime[i] = false;
               }
           }
       }
 
       // Function to print the position and
       // value of the primes in given matrix
       function printPrimes(arr, n) {
           // Traverse the matrix
           for (let i = 0; i < n; i++) {
               for (let j = 0; j < n; j++) {
 
                   // Check if the element is prime
                   // or not in O(1)
                   if (prime[arr[i][j]] == true) {
                       // Print the position and value
                       // if found true
                       document.write((i + 1) + " " + (j + 1) + " "
                           + (arr[i][j]) + "<br>");
                   }
               }
           }
       }
 
       // Driver Code
 
       let N = 2;
       let arr = new Array(N);
       let temp = [1, 2]
       arr[0] = temp;
       let temp1 = [2, 1]
       arr[1] = temp1;
 
       // Precomputing prime numbers using sieve
       SieveOfEratosthenes();
 
       // Find and print prime numbers
       // present in the matrix
       printPrimes(arr, N);
 
 
   // This code is contributed by Potta Lokesh
   </script>
Producción

1 2 2
2 1 2

Complejidad temporal: O(N*M) donde N*M es el tamaño de la array.
Espacio auxiliar: O(maxNum) donde maxNum es el elemento más grande de la array. 

Publicación traducida automáticamente

Artículo escrito por Code_r 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 *