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 : Sí
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