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.