Check if diagonal elements of a Matrix are Prime or not

0 0 6 minutes read

Given a matrix M[][] of dimension N*N, the task is to check if all the elements on the principal and cross diagonals of the matrix are prime or not. If found to be true, then print “Yes”. Otherwise print “No”.

Examples:

Input: M[][] = {{1, 2, 3, 13}, {5, 3, 7, 8}, {1, 2, 3, 4}, {5, 6, 7, 7}}
Output: Yes
Explanation:
Elements on the main diagonal are {1, 5, 3, 7}, which are all primes.
Elements on the cross diagonal are {13, 7, 2, 5}, which are all primes.
Therefore, the matrix satisfies all the necessary conditions.

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

Approach: The idea is to use Sieve of Eratosthenes to check if a number is prime or not. Follow the steps below to solve the problem:

Precompute and store the prime numbers using Sieve of Eratosthenes.
Iterate a loop using variable i over the range [0, N – 1] and perform the following operations:
- Check if M[i][i], i.e. an element on the principal diagonal, is a prime number or not.
- Check if M[i][N – 1 – i], i.e. an element on the cross diagonal, is a prime number or not.
- If any of the above two conditions are not satisfied, print “NO” and break.
Otherwise, print “YES”.

Below is the implementation of the above approach:

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>

Output

No

Time Complexity: O(N*log (log N))
Auxiliary Space: O(N)

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 zambiatek!