Dada una array A[][] de tamaño N*M , la tarea es comprobar si la array dada cumple o no las siguientes dos condiciones:
- La suma de todos los elementos es primo
- 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 SÍ 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