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 notbool prime[1000005];// Function to generate and store// primes using Sieve Of Eratosthenesvoid 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 notvoid 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 Codeint 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 approachimport java.io.*;import java.util.*;class GFG {// Stores if a number is prime or notstatic boolean[] prime = new boolean[1000005]; // Function to generate and store// primes using Sieve Of Eratosthenesstatic 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 notstatic 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 Codepublic 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 notprime = [True]*1000005# Function to generate and store# primes using Sieve Of Eratosthenesdef 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 notdef 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 Codeif __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 approachusing 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 notvar prime = Array(1000005).fill(true);// Function to generate and store// primes using Sieve Of Eratosthenesfunction 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 notfunction 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 Codevar M = [ [ 1, 2, 3, 13 ], [ 5, 3, 7, 8 ], [ 1, 2, 3, 4 ], [ 5, 6, 7, 7 ]];var N = M.length;// Function CallcheckElementsOnDiagonal(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
