Dada una array mat[][] de R filas y C columnas. La tarea es encontrar la suma de todos los elementos de la diagonal principal que son números primos .
Nota: Las diagonales principales son las que se encuentran desde la esquina superior izquierda de la array hasta la esquina inferior derecha.
Ejemplos:
Entrada: R = 3, C = 3, mat[][] = {{1, 2, 3}, {0, 1, 2}, {0, 4, 2}}
Salida: 2
Explicación:
Elementos de la diagonal principal son { 1, 1, 2}, de estos solo ‘2’ es un número primo.
Por tanto, la suma de los elementos primos de la diagonal = 2.Entrada: R = 4, C = 4, mat[][] = { {1, 2, 3, 4}, { 0, 7, 21, 12}, { 1, 2, 3, 6}, { 3, 5, 2, 31}}
Salida: 41
Explicación:
Los elementos de la diagonal principal son {1, 7, 3, 31}, de estos {7, 3, 31} son números primos.
Por tanto, la suma de los elementos primos de la diagonal = 7 + 3 + 31 = 41.
Enfoque ingenuo:
- Recorra la array dada y verifique si el elemento actual pertenece a la diagonal principal o no.
- Si el elemento pertenece a la diagonal principal y es un número primo, agregue el valor del elemento a totalSum.
- Después, el recorrido de la array imprime el valor de totalSum.
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;
// Function checks whether a number
// is prime or not
bool isPrime(int n)
{
if (n < 2) {
return false;
}
// Iterate to check primarility of n
for (int i = 2; i < n; i++) {
if (n % i == 0)
return false;
}
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
void primeDiagonalElementSum(
int* mat,
int r, int c)
{
// Initialise total sum as 0
int totalSum = 0;
// Iterate the given matrix mat[][]
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int temp = *((mat + i * c) + j);
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
cout << totalSum << endl;
}
// Driver Code
int main()
{
int R = 4, C = 5;
// Given Matrix
int mat[4][5] = { { 1, 2, 3, 4, 2 },
{ 0, 3, 2, 3, 9 },
{ 0, 4, 1, 2, 8 },
{ 1, 2, 3, 6, 6 } };
// Function Call
primeDiagonalElementSum((int*)mat, R, C);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function checks whether a number
// is prime or not
static boolean isPrime(int n)
{
if (n < 2)
{
return false;
}
// Iterate to check primarility of n
for(int i = 2; i < n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
static void primeDiagonalElementSum(int [][]mat,
int r, int c)
{
// Initialise total sum as 0
int totalSum = 0;
// Iterate the given matrix mat[][]
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
int temp = mat[i][j];
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
System.out.print(totalSum + "\n");
}
// Driver Code
public static void main(String[] args)
{
int R = 4, C = 5;
// Given Matrix
int mat[][] = { { 1, 2, 3, 4, 2 },
{ 0, 3, 2, 3, 9 },
{ 0, 4, 1, 2, 8 },
{ 1, 2, 3, 6, 6 } };
// Function Call
primeDiagonalElementSum(mat, R, C);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function checks whether a number # is prime or not def isPrime(n): if (n < 2): return False # Iterate to check primarility of n for i in range(2, n): if (n % i == 0): return False return True # Function calculates the sum of # prime elements of main diagonal def primeDiagonalElementSum(mat, r, c): # Initialise total sum as 0 totalSum = 0; # Iterate the given matrix mat[][] for i in range(r): for j in range(c): temp = mat[i][j] # If element belongs to main # diagonal and is prime if ((i == j) and isPrime(temp)): totalSum += (temp) # Print the total sum print(totalSum) # Driver code if __name__=="__main__": R = 4 C = 5 # Given Matrix mat = [ [ 1, 2, 3, 4, 2 ], [ 0, 3, 2, 3, 9 ], [ 0, 4, 1, 2, 8 ], [ 1, 2, 3, 6, 6 ] ] # Function call primeDiagonalElementSum(mat, R, C) # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
class GFG{
// Function checks whether a number
// is prime or not
public static bool isPrime(int n)
{
if (n < 2)
{
return false;
}
// Iterate to check primarility of n
for(int i = 2; i < n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
public static void primeDiagonalElementSum(int [,]mat,
int r, int c)
{
// Initialise total sum as 0
int totalSum = 0;
// Iterate the given matrix mat[][]
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
int temp = mat[i, j];
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
Console.WriteLine(totalSum);
}
// Driver Code
public static void Main(String[] args)
{
int R = 4, C = 5;
// Given Matrix
int [,]mat = { { 1, 2, 3, 4, 2 },
{ 0, 3, 2, 3, 9 },
{ 0, 4, 1, 2, 8 },
{ 1, 2, 3, 6, 6 } };
// Function Call
primeDiagonalElementSum(mat, R, C);
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// Javascript program for
// the above approach
// Function checks whether a number
// is prime or not
function isPrime( n)
{
if (n < 2)
{
return false;
}
// Iterate to check primarility of n
for(let i = 2; i < n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
function primeDiagonalElementSum(mat,r,c)
{
// Initialise total sum as 0
let totalSum = 0;
// Iterate the given matrix mat[][]
for(let i = 0; i < r; i++)
{
for(let j = 0; j < c; j++)
{
let temp = mat[i][j];
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
document.write(totalSum + "<br>");
}
// Driver Code
let R = 4, C = 5;
// Given Matrix
let mat = [[ 1, 2, 3, 4, 2 ],
[ 0, 3, 2, 3, 9 ],
[ 0, 4, 1, 2, 8 ],
[ 1, 2, 3, 6, 6 ]];
// Function Call
primeDiagonalElementSum(mat, R, C);
// This code is contributed by sravan kumar
</script>
Producción:
3
Complejidad temporal: O(R*C*K) , donde K es el elemento máximo de la array.
Espacio Auxiliar: O(1)
Enfoque eficiente: podemos optimizar el enfoque ingenuo optimizando la prueba de primariedad del número . A continuación se muestran los pasos para optimizar la prueba de primalidad:
- En lugar de verificar hasta N , podemos verificar hasta sqrt(N) ya que el factor más grande de N debe ser un múltiplo del factor más pequeño que ya se haya verificado.
- El algoritmo se puede mejorar aún más observando que todos los números primos tienen la forma 6k ± 1 , con la excepción de 2 y 3. Esto se debe a que todos los números enteros se pueden expresar como (6k + i) para algún número entero k y para i = – 1, 0, 1, 2, 3 o 4.
- Como 2 divide (6k + 0), (6k + 2), (6k + 4); y 3 divide (6k + 3). Entonces, un método más eficiente es probar si N es divisible por 2 o 3 , luego verificar todos los números de la forma 6k ± 1 .
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;
// Function checks whether a number
// is prime or not
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
void primeDiagonalElementSum(
int* mat,
int r, int c)
{
// Initialise total sum as 0
int totalSum = 0;
// Iterate the given matrix mat[][]
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int temp = *((mat + i * c) + j);
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
cout << totalSum << endl;
}
// Driver Code
int main()
{
int R = 4, C = 5;
// Given Matrix
int mat[4][5] = { { 1, 2, 3, 4, 2 },
{ 0, 3, 2, 3, 9 },
{ 0, 4, 1, 2, 8 },
{ 1, 2, 3, 6, 6 } };
// Function Call
primeDiagonalElementSum((int*)mat, R, C);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function checks whether a number
// is prime or not
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for(int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
static void primeDiagonalElementSum(int[][] mat,
int r, int c)
{
// Initialise total sum as 0
int totalSum = 0;
// Iterate the given matrix mat[][]
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
int temp = mat[i][j];
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
System.out.print(totalSum + "\n");
}
// Driver Code
public static void main(String[] args)
{
int R = 4, C = 5;
// Given Matrix
int mat[][] = { { 1, 2, 3, 4, 2 },
{ 0, 3, 2, 3, 9 },
{ 0, 4, 1, 2, 8 },
{ 1, 2, 3, 6, 6 } };
// Function call
primeDiagonalElementSum(mat, R, C);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function checks whether a number # is prime or not def isPrime(n): # Corner cases if (n <= 1): return False if (n <= 3): return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False i = 5 while i * i <= n: if (n % i == 0 or n % (i + 2) == 0): return False i += 6 return True # Function calculates the sum of # prime elements of main diagonal def primeDiagonalElementSum(mat, r, c): # Initialise total sum as 0 totalSum = 0 # Iterate the given matrix mat[][] for i in range(r): for j in range(c): temp = mat[i][j] # If element belongs to main # diagonal and is prime if ((i == j) and isPrime(temp)): totalSum += (temp) # Print the total sum print(totalSum) # Driver Code R, C = 4, 5 # Given Matrix mat = [ [ 1, 2, 3, 4, 2 ], [ 0, 3, 2, 3, 9 ], [ 0, 4, 1, 2, 8 ], [ 1, 2, 3, 6, 6 ] ] # Function Call primeDiagonalElementSum(mat, R, C) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
class GFG{
// Function checks whether a number
// is prime or not
static bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for(int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
static void primeDiagonalElementSum(int[,] mat,
int r, int c)
{
// Initialise total sum as 0
int totalSum = 0;
// Iterate the given matrix [,]mat
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
int temp = mat[i,j];
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
Console.Write(totalSum + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int R = 4, C = 5;
// Given Matrix
int [,]mat = { { 1, 2, 3, 4, 2 },
{ 0, 3, 2, 3, 9 },
{ 0, 4, 1, 2, 8 },
{ 1, 2, 3, 6, 6 } };
// Function call
primeDiagonalElementSum(mat, R, C);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program for the above approach
// Function checks whether a number
// is prime or not
function isPrime(n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (var i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function calculates the sum of
// prime elements of main diagonal
function primeDiagonalElementSum( mat, r, c)
{
// Initialise total sum as 0
var totalSum = 0;
// Iterate the given matrix mat[][]
for (var i = 0; i < r; i++) {
for (var j = 0; j < c; j++) {
var temp = mat[i][j];
// If element belongs to main
// diagonal and is prime
if ((i == j) && isPrime(temp))
totalSum += (temp);
}
}
// Print the total sum
document.write( totalSum );
}
// Driver Code
var R = 4, C = 5;
// Given Matrix
var mat = [ [ 1, 2, 3, 4, 2 ],
[ 0, 3, 2, 3, 9 ],
[ 0, 4, 1, 2, 8 ],
[ 1, 2, 3, 6, 6 ] ];
// Function Call
primeDiagonalElementSum(mat, R, C);
// This code is contributed by itsok.
</script>
Producción:
3
Complejidad temporal: O(R*C*sqrt(K)) , donde K es el elemento máximo de la array.
Espacio Auxiliar: O(1)
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