Given a matrix mat[][] of R rows and C columns. The task is to find the sum of all elements from the main diagonal which are prime numbers.
Note: The main diagonals are the ones that occur from Top Left of Matrix Down To Bottom Right Corner.
Examples:
Input: R = 3, C = 3, mat[][] = {{1, 2, 3}, {0, 1, 2}, {0, 4, 2}}
Output: 2
Explanation:
Elements from main diagonal are { 1, 1, 2}, out of these only ‘2’ is a prime number.
Therefore, the sum of diagonal elements which are prime = 2.Input: R = 4, C = 4, mat[][] = { {1, 2, 3, 4}, { 0, 7, 21, 12}, { 1, 2, 3, 6}, { 3, 5, 2, 31}}
Output: 41
Explanation:
Elements from main diagonal are { 1, 7, 3, 31}, out of these {7, 3, 31} are prime numbers.
Therefore, the sum of diagonal elements which are prime = 7 + 3 + 31 = 41.
Naive Approach:
- Traverse the given matrix and check if the current element belongs to main diagonal or not.
- If element belongs to the main diagonal and it is a prime number then add value of the element to totalSum.
- After, traversal of the matrix print the value of totalSum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function checks whether a number// is prime or notbool isPrime(int n){ if (n < 2) { return false; } // Iterate to check primality 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 diagonalvoid 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 Codeint 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 approachclass GFG{// Function checks whether a number// is prime or notstatic 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 diagonalstatic 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 Codepublic 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 notdef 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 diagonaldef 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 codeif __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 approachusing System;class GFG{// Function checks whether a number// is prime or notpublic 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 diagonalpublic 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 Codepublic 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 notfunction 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 diagonalfunction 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> |
Output:
3
Time Complexity: O(R*C*K), where K is the maximum element in the matrix.
Auxiliary Space: O(1)
Efficient Approach: We can optimize the naive approach by optimizing the primality test of the number. Below are the steps for optimizing the primality test:
- Instead of checking till N, we can check till sqrt(N) as the larger factor of N must be a multiple of smaller factor that has been already checked.
- The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = -1, 0, 1, 2, 3, or 4.
- As 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if N is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function checks whether a number// is prime or notbool 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 diagonalvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Function checks whether a number// is prime or notstatic 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 diagonalstatic 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 Codepublic 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 notdef 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 diagonaldef 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 CodeR, C = 4, 5# Given Matrixmat = [ [ 1, 2, 3, 4, 2 ], [ 0, 3, 2, 3, 9 ], [ 0, 4, 1, 2, 8 ], [ 1, 2, 3, 6, 6 ] ]# Function CallprimeDiagonalElementSum(mat, R, C)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;class GFG{// Function checks whether a number// is prime or notstatic 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 diagonalstatic 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 Codepublic 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 notfunction 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 diagonalfunction 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 Codevar R = 4, C = 5;// Given Matrixvar mat = [ [ 1, 2, 3, 4, 2 ], [ 0, 3, 2, 3, 9 ], [ 0, 4, 1, 2, 8 ], [ 1, 2, 3, 6, 6 ] ];// Function CallprimeDiagonalElementSum(mat, R, C);// This code is contributed by itsok.</script> |
Output:
3
Time Complexity: O(R*C*sqrt(K)), where K is the maximum element in the matrix.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
