Comprobar si los elementos diagonales de una array son primos o no

Dada una array M[][] de dimensión N*N , la tarea es comprobar si todos los elementos de las diagonales principal y transversal de la array son primos o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba «No».

Ejemplos:

Entrada: M[][] = {{1, 2, 3, 13}, {5, 3, 7, 8}, {1, 2, 3, 4}, {5, 6, 7, 7}}
Salida :
Explicación:
Los elementos de la diagonal principal son {1, 5, 3, 7}, que son todos primos.
Los elementos de la diagonal transversal son {13, 7, 2, 5}, que son todos primos.
Por lo tanto, la array satisface todas las condiciones necesarias.

Entrada: M[][] = {{1, 2, 3}, {5, 3, 7}, {5, 6, 4}}
Salida: No

Planteamiento: La idea es utilizar la Criba de Eratóstenes para comprobar si un número es primo o no . Siga los pasos a continuación para resolver el problema:

  • Precalcule y almacene los números primos usando la criba de Eratóstenes .
  • Itere un ciclo usando la variable i sobre el rango [0, N – 1] y realice las siguientes operaciones: 
    • Comprueba si M[i][i], es decir, un elemento de la diagonal principal, es un número primo o no.
    • Compruebe si M[i][N – 1 – i], es decir, un elemento en la diagonal transversal, es un número primo o no.
    • Si alguna de las dos condiciones anteriores no se cumple, escriba «NO» y rompa .
  • De lo contrario, escriba “SI” .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores if a number is prime or not
bool prime[1000005];
 
// Function to generate and store
// primes using Sieve Of Eratosthenes
void SieveOfEratosthenes(int N)
{
    // Set all numbers as prime
    memset(prime, true, sizeof(prime));
 
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p <= N; p++) {
 
        // If p is a prime
        if (prime[p] == true) {
 
            // Set all its multiples
            // as non-prime
            for (int i = p * p;
                 i <= N; i += p)
 
                prime[i] = false;
        }
    }
}
 
// Function to check if all diagonal
// elements are prime or not
void checkElementsOnDiagonal(
    vector<vector<int> > M, int N)
{
    // Stores if all diagonal
    // elements are prime or not
    int flag = 1;
 
    // Precompute primes
    SieveOfEratosthenes(1000000);
 
    // Traverse the range [0, N-1]
    for (int i = 0; i < N; i++) {
 
        // Check if numbers on the cross
        // diagonal and main diagonal
        // are primes or not
        flag &= (prime[M[i][i]]
                 && prime[M[i][N - 1 - i]]);
    }
 
    // If true, then print "Yes"
    if (flag)
        cout << "Yes" << endl;
 
    // Otherwise, print "No"
    else
        cout << "No";
}
 
// Driver Code
int main()
{
    vector<vector<int> > M = {
        { 1, 2, 3, 13 },
        { 5, 3, 7, 8 },
        { 1, 2, 3, 4 },
        { 5, 6, 7, 7 }
    };
    int N = M.size();
 
    // Function Call
    checkElementsOnDiagonal(M, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
// Stores if a number is prime or not
static boolean[] prime = new boolean[1000005];
  
// Function to generate and store
// primes using Sieve Of Eratosthenes
static void SieveOfEratosthenes(int N)
{
   
    // Set all numbers as prime
    Arrays.fill(prime, true);
 
    prime[0] = false;
    prime[1] = false;
  
    for (int p = 2; p * p <= N; p++) {
  
        // If p is a prime
        if (prime[p] == true) {
  
            // Set all its multiples
            // as non-prime
            for (int i = p * p;
                 i <= N; i += p)
  
                prime[i] = false;
        }
    }
}
  
// Function to check if all diagonal
// elements are prime or not
static void checkElementsOnDiagonal(int[][] M, int N)
{
   
    // Stores if all diagonal
    // elements are prime or not
    int flag = 1;
  
    // Precompute primes
    SieveOfEratosthenes(1000000);
  
    // Traverse the range [0, N-1]
    for (int i = 0; i < N; i++) {
  
        // Check if numbers on the cross
        // diagonal and main diagonal
        // are primes or not
        boolean flg = (boolean)(prime[M[i][i]]
                && prime[M[i][N - 1 - i]]);
        int val = (flg) ? 1 : 0;
        flag &= val;
    }
  
    // If true, then print "Yes"
    if (flag != 0)
        System.out.print("Yes");
  
    // Otherwise, print "No"
    else
        System.out.print("No");
}
 
 
// Driver Code
public static void main (String[] args)
{
     
    int[][] M = {
        { 1, 2, 3, 13 },
        { 5, 3, 7, 8 },
        { 1, 2, 3, 4 },
        { 5, 6, 7, 7 }
    };
    int N = M.length;
  
    // Function Call
    checkElementsOnDiagonal(M, N);
}
}
 
// This code is contributed by code_hunt.

Python3

# Python3 program for the above approach
 
# Stores if a number is prime or not
prime = [True]*1000005
 
# Function to generate and store
# primes using Sieve Of Eratosthenes
def SieveOfEratosthenes(N):
   
    # Set all numbers as prime
    # memset(prime, true, sizeof(prime))
    prime[0] = False
    prime[1] = False
 
    for p in range(2, N + 1):
        if p * p > N:
            break
             
        # If p is a prime
        if (prime[p] == True):
 
            # Set all its multiples
            # as non-prime
            for i in range(p * p, N + 1, p):
                prime[i] = False
 
# Function to check if all diagonal
# elements are prime or not
def checkElementsOnDiagonal(M, N):
   
    # Stores if all diagonal
    # elements are prime or not
    flag = 1
 
    # Precompute primes
    SieveOfEratosthenes(1000000)
 
    # Traverse the range [0, N-1]
    for i in range(N):
 
        # Check if numbers on the cross
        # diagonal and main diagonal
        # are primes or not
        flag &= (prime[M[i][i]] and prime[M[i][N - 1 - i]])
 
    # If true, then print"Yes"
    if (flag):
        print("Yes")
 
    # Otherwise, print "No"
    else:
        print("No")
 
# Driver Code
if __name__ == '__main__':
    M = [[ 1, 2, 3, 13 ],
        [ 5, 3, 7, 8 ],
        [ 1, 2, 3, 4 ],
        [ 5, 6, 7, 7 ]]
    N = len(M)
 
    # Function Call
    checkElementsOnDiagonal(M, N)
 
    # This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
class GFG
{
 
  // Stores if a number is prime or not
  static bool[] prime = new bool[1000005];
 
  // Function to generate and store
  // primes using Sieve Of Eratosthenes
  static void SieveOfEratosthenes(int N)
  {
 
    // Set all numbers as prime
    Array.Fill(prime, true);
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= N; p++) {
 
      // If p is a prime
      if (prime[p] == true) {
 
        // Set all its multiples
        // as non-prime
        for (int i = p * p; i <= N; i += p)
 
          prime[i] = false;
      }
    }
  }
 
  // Function to check if all diagonal
  // elements are prime or not
  static void checkElementsOnDiagonal(int[, ] M, int N)
  {
 
    // Stores if all diagonal
    // elements are prime or not
    int flag = 1;
 
    // Precompute primes
    SieveOfEratosthenes(1000000);
 
    // Traverse the range [0, N-1]
    for (int i = 0; i < N; i++) {
 
      // Check if numbers on the cross
      // diagonal and main diagonal
      // are primes or not
      bool flg = (bool)(prime[M[i, i]]
                        && prime[M[i, N - 1 - i]]);
      int val = (flg) ? 1 : 0;
      flag &= val;
    }
 
    // If true, then print "Yes"
    if (flag != 0)
      Console.Write("Yes");
 
    // Otherwise, print "No"
    else
      Console.Write("No");
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
 
    int[, ] M = { { 1, 2, 3, 13 },
                 { 5, 3, 7, 8 },
                 { 1, 2, 3, 4 },
                 { 5, 6, 7, 7 } };
    int N = M.GetLength(0);
 
    // Function Call
    checkElementsOnDiagonal(M, N);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript program for the above approach
 
// Stores if a number is prime or not
var prime = Array(1000005).fill(true);
 
// Function to generate and store
// primes using Sieve Of Eratosthenes
function SieveOfEratosthenes(N)
{
    // Set all numbers as prime
 
    prime[0] = false;
    prime[1] = false;
 
    for (var p = 2; p * p <= N; p++) {
 
        // If p is a prime
        if (prime[p] == true) {
 
            // Set all its multiples
            // as non-prime
            for (var i = p * p;
                 i <= N; i += p)
 
                prime[i] = false;
        }
    }
}
 
// Function to check if all diagonal
// elements are prime or not
function checkElementsOnDiagonal( M, N)
{
    // Stores if all diagonal
    // elements are prime or not
    var flag = 1;
 
    // Precompute primes
    SieveOfEratosthenes(1000000);
 
    // Traverse the range [0, N-1]
    for (var i = 0; i < N; i++) {
 
        // Check if numbers on the cross
        // diagonal and main diagonal
        // are primes or not
        flag &= (prime[M[i][i]]
                 && prime[M[i][N - 1 - i]]);
    }
 
    // If true, then print "Yes"
    if (flag)
        document.write( "Yes" );
 
    // Otherwise, print "No"
    else
        document.write( "No");
}
 
// Driver Code
var M = [
    [ 1, 2, 3, 13 ],
    [ 5, 3, 7, 8 ],
    [ 1, 2, 3, 4 ],
    [ 5, 6, 7, 7 ]
];
var N = M.length;
 
// Function Call
checkElementsOnDiagonal(M, N);
 
// This code is contributed by noob2000.
</script>
Producción

No

Complejidad de tiempo: O(N*log (log N))
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 *