Compruebe si Matrix sigue las restricciones dadas o no

Dada una array A[][] de tamaño N*M , la tarea es comprobar si la array dada cumple o no las siguientes dos condiciones:

  1. La suma de todos los elementos es primo
  2. El elemento A[i][j] de la array también debería ser primo si (i + j) es primo.

Ejemplos:

Entrada: N = 4, M = 5 
A[][] = {{ 1, 2, 3, 2, 2 }, { 2, 2, 7, 7, 7 }, { 7, 7, 21, 7, 10 }, { 2, 2, 3, 6, 7 }} 
Salida: SÍ 
Explicación: 
Suma de todos los elementos = 107 (primos) 
Todos los posibles (i, j) tales que (i + j) son primos son: 
(0+2 ) = 2 (primo) y A[0][2] = 3 (primo) 
(0+3) = 3 (primo) y A[0][3] = 2 (primo) 
(1+1) = 2 ( prima) y A[1][1] = 2 (prima) 
(1+2) = 3 (prima) y A[1][2] = 7 (prima) 
(1+4) = 5 (prima) y A [1][4] = 7 (primo) 
(2+0) = 2 (primo) y A[2][0] = 7 (primo) 
(2+1) = 3 (primo) y A[2][ 1] = 7 (primo) 
(2+3) = 5 (primo) y A[2][3] = 7 (primo) 
(3+0) = 3 (primo) y A[3][0] = 2 (principal) 
(3+2) = 5 (primo) y A[3][2] = 3 (primo) 
(3+4) = 7 (primo) y A[3][4] = 7 (primo) 
Por lo tanto, ambas condiciones están satisfechos y la respuesta es SÍ.

Entrada: N = 3, M = 3 
A[][] = {{7, 3, 4}, {11, 0, 6}, {12, 16, 3}} 
Salida: NO 
Explicación: 
Suma de todos los elementos = 62 (no primo) 
Por lo tanto, la primera condición no se cumple.

Enfoque ingenuo: 
calcule la suma de todos los elementos en la array y verifique si es primo. Si no, escriba NO . De lo contrario, atraviese toda la array y para cada (i, j) tal que (i + j) sea primo, verifique si A[ i ][ j ] es primo. Si se cumplen ambas condiciones para todos los valores de (i, j), imprima como salida. De lo contrario, imprima NO . La prueba de primalidad para un número K se puede realizar usando fuerza bruta simple en O(√K). 

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

C++

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function checks if
// n is prime or not
 
bool isPrime(int n)
{
 
    // Corner case
 
    if (n <= 1)
        return false;
 
    // Check from 2 to sqrt(n)
 
    for (int i = 2; i <= sqrt(n);
         i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 
// Function returns sum of
// all elements of matrix
 
int takeSum(int a[4][5])
{
    // Stores the sum of the matrix
    int sum = 0;
 
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            sum += a[i][j];
 
    return sum;
}
 
// Function to check if all a[i][j]
// with prime (i+j) are prime
bool checkIndex(int n, int m,
                int a[4][5])
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            // If index is prime
            if (isPrime(i + j)) {
 
                // If element not prime
                if (!isPrime(a[i][j]))
                    return false;
            }
        }
    }
    return true;
}
 
// Driver code
int main()
{
 
    int n = 4, m = 5;
 
    int a[4][5] = { { 1, 2, 3, 2, 2 },
                    { 2, 2, 7, 7, 7 },
                    { 7, 7, 21, 7, 10 },
                    { 2, 2, 3, 6, 7 } };
 
    int sum = takeSum(a);
 
    // Check for both conditions
    if (isPrime(sum)
        && checkIndex(n, m, a)) {
 
        cout << "YES" << endl;
    }
    else
        cout << "NO" << endl;
 
    return 0;
}

Java

// Java implementation of
// the above approach
class GFG{
 
// Function checks if
// n is prime or not
static boolean isPrime(int n)
{
     
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to Math.sqrt(n)
    for(int i = 2; i <= Math.sqrt(n); i++)
       if (n % i == 0)
           return false;
 
    return true;
}
 
// Function returns sum of
// all elements of matrix
static int takeSum(int a[][])
{
     
    // Stores the sum of the matrix
    int sum = 0;
 
    for(int i = 0; i < 4; i++)
       for(int j = 0; j < 5; j++)
          sum += a[i][j];
           
    return sum;
}
 
// Function to check if all a[i][j]
// with prime (i+j) are prime
static boolean checkIndex(int n, int m,
                          int a[][])
{
    for(int i = 0; i < n; i++)
    {
       for(int j = 0; j < m; j++)
       {
            
          // If index is prime
          if (isPrime(i + j))
          {
              // If element not prime
              if (!isPrime(a[i][j]))
                  return false;
          }
       }
    }
    return true;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 4, m = 5;
 
    int a[][] = { { 1, 2, 3, 2, 2 },
                  { 2, 2, 7, 7, 7 },
                  { 7, 7, 21, 7, 10 },
                  { 2, 2, 3, 6, 7 } };
 
    int sum = takeSum(a);
 
    // Check for both conditions
    if (isPrime(sum) && checkIndex(n, m, a))
    {
        System.out.print("YES" + "\n");
    }
    else
    {
        System.out.print("NO" + "\n");
    }
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of
# the above approach
import math
 
# Function checks if
# n is prime or not
def isPrime(n):
 
    # Corner case
    if (n <= 1):
        return False
 
    # Check from 2 to sqrt(n)
    for i in range(2, int(math.sqrt(n)) + 1):
        if (n % i == 0):
            return False
 
    return True
 
# Function returns sum of
# all elements of matrix
def takeSum(a, n, m):
     
    # Stores the sum of the matrix
    sum = 0
 
    for i in range(0, n):
        for j in range(0, m):
            sum += a[i][j]
 
    return sum
 
# Function to check if all a[i][j]
# with prime (i+j) are prime
def checkIndex(n, m, a):
     
    for i in range(0, n):
        for j in range(0, m):
 
            # If index is prime
            if (isPrime(i + j)):
 
                # If element not prime
                if (isPrime(a[i][j]) != True):
                    return False
     
    return True
 
# Driver code
n = 4
m = 5
 
a = [ [ 1, 2, 3, 2, 2 ] ,
      [ 2, 2, 7, 7, 7 ],
      [ 7, 7, 21, 7, 10 ],
      [ 2, 2, 3, 6, 7 ] ]
 
sum = takeSum(a, n, m)
 
# Check for both conditions
if (isPrime(sum) and checkIndex(n, m, a)):
    print("YES")
else:
    print("NO")
 
# This code is contributed by sanjoy_62

C#

// C# implementation of
// the above approach
using System;
 
class GFG{
 
// Function checks if
// n is prime or not
static bool isPrime(int n)
{
     
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to Math.Sqrt(n)
    for(int i = 2; i <= Math.Sqrt(n); i++)
       if (n % i == 0)
           return false;
 
    return true;
}
 
// Function returns sum of
// all elements of matrix
static int takeSum(int[,]a)
{
     
    // Stores the sum of the matrix
    int sum = 0;
 
    for(int i = 0; i < 4; i++)
       for(int j = 0; j < 5; j++)
          sum += a[i, j];
             
    return sum;
}
 
// Function to check if all a[i,j]
// with prime (i+j) are prime
static bool checkIndex(int n, int m,
                       int[,]a)
{
    for(int i = 0; i < n; i++)
    {
       for(int j = 0; j < m; j++)
       {
            
          // If index is prime
          if (isPrime(i + j))
          {
 
              // If element not prime
              if (!isPrime(a[i, j]))
                  return false;
          }
       }
    }
    return true;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 4, m = 5;
 
    int[,]a = { { 1, 2, 3, 2, 2 },
                { 2, 2, 7, 7, 7 },
                { 7, 7, 21, 7, 10 },
                { 2, 2, 3, 6, 7 } };
 
    int sum = takeSum(a);
 
    // Check for both conditions
    if (isPrime(sum) && checkIndex(n, m, a))
    {
        Console.Write("YES" + "\n");
    }
    else
    {
        Console.Write("NO" + "\n");
    }
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Stores true at prime
// indices
let prime = [];
  
// Function to generate
// the prime numbers
// using Sieve of Eratosthenes
function buildSieve(sum)
{
    prime = Array.from({length: sum + 1}, (_, i) => 1);
  
    prime[0] = false;
    prime[1] = false;
  
    for(let p = 2; p * p < (sum + 1); p++)
    {
  
        // If p is still true
        if (prime[p] == true)
        {
              
            // Mark all multiples of p
            for(let i = p * 2;
                    i < (sum + 1);
                    i += p)
                prime[i] = false;
        }
    }
}
  
// Function returns sum of
// all elements of matrix
function getSum(a)
{
    let s = 0;
    for(let i = 0; i < 4; i++)
        for(let j = 0; j < 5; j++)
            s += a[i][j];
  
    return s;
}
  
// Function to check if for all
// prime (i+j), a[i][j] is prime
function checkIndex(n, m, a)
{
    for(let i = 0; i < n; i++)
        for(let j = 0; j < m; j++)
        {
              
            // If index is prime
            if (prime[i + j] &&
               !prime[a[i][j]])
            {
                return false;
            }
        }
    return true;
}
 
// Driver code
 
      let n = 4, m = 5;
  
    let a = [[ 1, 2, 3, 2, 2 ],
                  [ 2, 2, 7, 7, 7 ],
                  [ 7, 7, 21, 7, 10 ],
                  [ 2, 2, 3, 6, 7 ]];
  
    let sum = getSum(a);
  
    buildSieve(sum);
  
    // Check for both conditions
    if (prime[sum] && checkIndex(n, m, a))
    {
        document.write("YES" + "<br/>");
    }
    else{
        document.write("NO" + "<br/>");
    }
     
    // This code is contributed by code_hunt.
</script>
Producción: 

YES

 

Complejidad temporal: O(N * M * √K) 
Espacio auxiliar: O(1)

Enfoque eficiente: 
para optimizar el enfoque anterior, podemos realizar una prueba de primalidad utilizando Tamiz de Eratóstenes . Almacene los números primos hasta sum , que denota la suma de los elementos de la array. Esto reduce la complejidad computacional de la prueba de primalidad a O(1) y el cálculo previo del tamiz requiere O(log(log(sum))) .

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

C++

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores true at prime
// indices
vector<bool> prime;
 
// Function to generate
// the prime numbers
// using Sieve of Eratosthenes
void buildSieve(int sum)
{
    prime = vector<bool>(sum + 1,
                         true);
 
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p
                    < (sum + 1);
         p++) {
 
        // If p is still true
        if (prime[p] == true) {
 
            // Mark all multiples of p
            for (int i = p * 2;
                 i < (sum + 1);
                 i += p)
                prime[i] = false;
        }
    }
}
 
// Function returns sum of
// all elements of matrix
int getSum(int a[4][5])
{
 
    int s = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            s += a[i][j];
 
    return s;
}
 
// Function to check if for all
// prime (i+j), a[i][j] is prime
bool checkIndex(int n, int m,
                int a[4][5])
{
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
 
            // If index is prime
            if (prime[i + j]
                && !prime[a[i][j]]) {
                return false;
            }
        }
    return true;
}
 
// Driver Code
int main()
{
 
    int n = 4, m = 5;
 
    int a[4][5] = { { 1, 2, 3, 2, 2 },
                    { 2, 2, 7, 7, 7 },
                    { 7, 7, 21, 7, 10 },
                    { 2, 2, 3, 6, 7 } };
 
    int sum = getSum(a);
 
    buildSieve(sum);
 
    // Check for both conditions
    if (prime[sum] && checkIndex(n, m, a)) {
        cout << "YES" << endl;
    }
    else
        cout << "NO" << endl;
 
    return 0;
}

Java

// Java implementation of
// the above approach
import java.util.*;
 
class GFG{
 
// Stores true at prime
// indices
static boolean []prime;
 
// Function to generate
// the prime numbers
// using Sieve of Eratosthenes
static void buildSieve(int sum)
{
    prime = new boolean[sum + 1];
    Arrays.fill(prime, true);
 
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p < (sum + 1); p++)
    {
 
        // If p is still true
        if (prime[p] == true)
        {
             
            // Mark all multiples of p
            for(int i = p * 2;
                    i < (sum + 1);
                    i += p)
                prime[i] = false;
        }
    }
}
 
// Function returns sum of
// all elements of matrix
static int getSum(int a[][])
{
    int s = 0;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 5; j++)
            s += a[i][j];
 
    return s;
}
 
// Function to check if for all
// prime (i+j), a[i][j] is prime
static boolean checkIndex(int n, int m,
                          int a[][])
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
             
            // If index is prime
            if (prime[i + j] &&
               !prime[a[i][j]])
            {
                return false;
            }
        }
    return true;
}
 
// Driver Code
public static void main(String[] args)
{
 
    int n = 4, m = 5;
 
    int a[][] = { { 1, 2, 3, 2, 2 },
                  { 2, 2, 7, 7, 7 },
                  { 7, 7, 21, 7, 10 },
                  { 2, 2, 3, 6, 7 } };
 
    int sum = getSum(a);
 
    buildSieve(sum);
 
    // Check for both conditions
    if (prime[sum] && checkIndex(n, m, a))
    {
        System.out.print("YES" + "\n");
    }
    else
        System.out.print("NO" + "\n");
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 implementation of
# the above approach
  
# Stores true at prime
# indices
prime = []
  
# Function to generate
# the prime numbers
# using Sieve of Eratosthenes
def buildSieve(sum):
     
    global prime
    prime = [True for i in range(sum + 1)]
  
    prime[0] = False
    prime[1] = False
     
    p = 2
     
    while(p * p < (sum + 1)):
  
        # If p is still true
        if (prime[p]):
  
            # Mark all multiples of p
            for i in range(p * 2, sum + 1, p):
                prime[i] = False
                 
        p += 1
         
# Function returns sum of
# all elements of matrix
def getSum(a):
     
    s = 0
     
    for i in range(4):
        for j in range(5):
            s += a[i][j]
  
    return s
 
# Function to check if for all
# prime (i+j), a[i][j] is prime
def checkIndex(n, m, a):
  
    for i in range(n):
        for j in range(m):
  
            # If index is prime
            if (prime[i + j] and
            not prime[a[i][j]]):
                return False
                 
    return True
     
# Driver code
if __name__=="__main__":
     
    n = 4
    m = 5
  
    a = [ [ 1, 2, 3, 2, 2 ],
          [ 2, 2, 7, 7, 7 ],
          [ 7, 7, 21, 7, 10 ],
          [ 2, 2, 3, 6, 7 ] ]
  
    sum = getSum(a)
  
    buildSieve(sum)
     
    # Check for both conditions
    if (prime[sum] and checkIndex(n, m, a)):
        print("YES")
    else:
        print("NO")
     
# This code is contributed by rutvik_56

C#

// C# implementation of
// the above approach
using System;
 
class GFG{
 
// Stores true at prime
// indices
static bool []prime;
 
// Function to generate
// the prime numbers
// using Sieve of Eratosthenes
static void buildSieve(int sum)
{
    prime = new bool[sum + 1];
    for(int i = 0; i < prime.Length; i++)
        prime[i] = true;
 
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p < (sum + 1); p++)
    {
 
        // If p is still true
        if (prime[p] == true)
        {
             
            // Mark all multiples of p
            for(int i = p * 2;
                    i < (sum + 1);
                    i += p)
                prime[i] = false;
        }
    }
}
 
// Function returns sum of
// all elements of matrix
static int getSum(int[,]a)
{
    int s = 0;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 5; j++)
            s += a[i, j];
 
    return s;
}
 
// Function to check if for all
// prime (i+j), a[i,j] is prime
static bool checkIndex(int n, int m,
                       int[,]a)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
             
            // If index is prime
            if (prime[i + j] &&
               !prime[a[i, j]])
            {
                return false;
            }
        }
    }
    return true;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 4, m = 5;
 
    int[,]a = { { 1, 2, 3, 2, 2 },
                { 2, 2, 7, 7, 7 },
                { 7, 7, 21, 7, 10 },
                { 2, 2, 3, 6, 7 } };
 
    int sum = getSum(a);
 
    buildSieve(sum);
 
    // Check for both conditions
    if (prime[sum] && checkIndex(n, m, a))
    {
        Console.Write("YES" + "\n");
    }
    else
        Console.Write("NO" + "\n");
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript implementation of
// the above approach
 
// Stores true at prime
// indices
var prime = [];
 
// Function to generate
// the prime numbers
// using Sieve of Eratosthenes
function buildSieve(sum)
{
    prime = Array(sum+1).fill(true);
 
    prime[0] = false;
    prime[1] = false;
 
    for (var p = 2; p * p
                    < (sum + 1);
         p++) {
 
        // If p is still true
        if (prime[p] == true) {
 
            // Mark all multiples of p
            for (var i = p * 2;
                 i < (sum + 1);
                 i += p)
                prime[i] = false;
        }
    }
}
 
// Function returns sum of
// all elements of matrix
function getSum(a)
{
 
    var s = 0;
    for (var i = 0; i < 4; i++)
        for (var j = 0; j < 5; j++)
            s += a[i][j];
 
    return s;
}
 
// Function to check if for all
// prime (i+j), a[i][j] is prime
function checkIndex(n, m, a)
{
 
    for (var i = 0; i < n; i++)
        for (var j = 0; j < m; j++) {
 
            // If index is prime
            if (prime[i + j]
                && !prime[a[i][j]]) {
                return false;
            }
        }
    return true;
}
 
// Driver Code
var n = 4, m = 5;
var a = [ [ 1, 2, 3, 2, 2 ],
                [ 2, 2, 7, 7, 7 ],
                [ 7, 7, 21, 7, 10 ],
                [ 2, 2, 3, 6, 7 ] ];
var sum = getSum(a);
buildSieve(sum);
// Check for both conditions
if (prime[sum] && checkIndex(n, m, a)) {
    document.write( "YES" );
}
else
    document.write( "NO" );
 
// This code is contributed by itsok.
</script>
Producción: 

YES

 

Complejidad temporal: O(log(log(sum)) + (N*M)), donde sum denota la suma de la array. 
Espacio Auxiliar: O(N) 
 

Publicación traducida automáticamente

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