Given a 2d array mat[][], the task is to find and print the prime numbers along with their position (1-based indexing) in this 2d array.
Examples:
Input: mat[][] = {{1, 2}, {2, 1}}
Output:
1 2 2
2 1 2
Explanation: First prime is at position row 1 and column 2 and the value is 2
Second prime is at position row 2 and column 1 and the value is 2
Input: mat[][] = {{1, 1}, {1, 1}}
Output: -1
Explanation: There is no prime number in this 2d array
Naive Approach: The basic idea is to traverse the 2d array and for each number, check whether it is prime or not. If it is prime, print the position and the value for each found prime number.
Time Complexity: O(NM*sqrt(X)), where N*M is the size of the matrix and X is the largest element in the matrix
Auxiliary Space: O(1)
Efficient Approach: We can efficiently check if the number is prime or not using sieve. Then traverse the 2d array and simply check if the number is prime or not in O(1).
Follow the below steps for implementing this approach:
- Find the maximum element from the matrix and store it in a variable maxNum.
- Now find the prime numbers from 1 to maxNum using sieve of eratosthenes and store the result in array prime[].
- Now traverse the matrix and for each number check if it is a prime or not using the prime[] array.
- For each prime number in matrix print its position (row, column) and value.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;#define MAXN 100001bool prime[MAXN];// Function to find prime numbers using sievevoid SieveOfEratosthenes(){ int n = MAXN - 1; // Create a boolean array // "prime[0..n]" and initialize // all entries it as true. // A value in prime[i] will // finally be false if i is // Not a prime, else true. memset(prime, true, sizeof(prime)); prime[0] = false; prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } }}// Function to print the position and// value of the primes in given matrixvoid printPrimes(vector<vector<int> >& arr, int n){ // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check if the element is prime // or not in O(1) if (prime[arr[i][j]] == true) { // Print the position and value // if found true cout << i + 1 << " " << j + 1 << " " << arr[i][j] << endl; } } }}// Driver Codeint main(){ int N = 2; vector<vector<int> > arr; vector<int> temp(N, 2); temp[0] = 1; temp[1] = 2; arr.push_back(temp); temp[0] = 2; temp[1] = 1; arr.push_back(temp); // Precomputing prime numbers using sieve SieveOfEratosthenes(); // Find and print prime numbers // present in the matrix printPrimes(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { static int MAXN = 100001; static boolean prime[] = new boolean[MAXN]; // Function to find prime numbers using sieve static void SieveOfEratosthenes() { int n = MAXN - 1; Arrays.fill(prime, true); // Create a boolean array // "prime[0..n]" and initialize // all entries it as true. // A value in prime[i] will // finally be false if i is // Not a prime, else true. prime[0] = false; prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (int i = p * p; i <= n; i = i + p) prime[i] = false; } } } // Function to print the position and // value of the primes in given matrix static void printPrimes(int[][] arr, int n) { // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check if the element is prime // or not in O(1) if (prime[arr[i][j]] == true) { // Print the position and value // if found true System.out.print((i + 1)); System.out.print(" "); System.out.print(j + 1); System.out.print(" "); System.out.print(arr[i][j]); System.out.println(); } } } } // Driver Code public static void main(String[] args) { int N = 2; int arr[][] = new int[N][N]; arr[0][0] = 1; arr[0][1] = 2; arr[1][0] = 2; arr[1][1] = 1; // Precomputing prime numbers using sieve SieveOfEratosthenes(); // Find and print prime numbers // present in the matrix printPrimes(arr, N); }}// This code is contributed by Potta Lokesh |
Python3
# python code to implement the above approachimport mathMAXN = 100001prime = [True for _ in range(MAXN)]# Function to find prime numbers using sievedef SieveOfEratosthenes(): global prime n = MAXN - 1 # Create a boolean array # "prime[0..n]" and initialize # all entries it as true. # A value in prime[i] will # finally be false if i is # Not a prime, else true. prime[0] = False prime[1] = False for p in range(2, int(math.sqrt(n)) + 1): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples # of p greater than or # equal to the square of it # numbers which are multiple # of p and are less than p^2 # are already been marked. for i in range(p*p, n+1, p): prime[i] = False# Function to print the position and# value of the primes in given matrixdef printPrimes(arr, n): # Traverse the matrix for i in range(0, n): for j in range(0, n): # Check if the element is prime # or not in O(1) if (prime[arr[i][j]] == True): # Print the position and value # if found true print(f"{i + 1} {j + 1} {arr[i][j]}")# Driver Codeif __name__ == "__main__": N = 2 arr = [] temp = [2 for _ in range(N)] temp[0] = 1 temp[1] = 2 arr.append(temp.copy()) temp[0] = 2 temp[1] = 1 arr.append(temp.copy()) # Precomputing prime numbers using sieve SieveOfEratosthenes() # Find and print prime numbers # present in the matrix printPrimes(arr, N) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { static int MAXN = 100001; static bool[] prime = new bool[MAXN]; // Function to find prime numbers using sieve static void SieveOfEratosthenes() { int n = MAXN - 1; Array.Fill(prime, true); // Create a boolean array // "prime[0..n]" and initialize // all entries it as true. // A value in prime[i] will // finally be false if i is // Not a prime, else true. prime[0] = false; prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (int i = p * p; i <= n; i = i + p) prime[i] = false; } } } // Function to print the position and // value of the primes in given matrix static void printPrimes(int[,] arr, int n) { // Traverse the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check if the element is prime // or not in O(1) if (prime[arr[i,j]] == true) { // Print the position and value // if found true Console.Write((i + 1)); Console.Write(" "); Console.Write(j + 1); Console.Write(" "); Console.Write(arr[i,j]); Console.WriteLine(); } } } } // Driver Code public static void Main(String[] args) { int N = 2; int[,] arr = new int[N,N]; arr[0,0] = 1; arr[0,1] = 2; arr[1,0] = 2; arr[1,1] = 1; // Precomputing prime numbers using sieve SieveOfEratosthenes(); // Find and print prime numbers // present in the matrix printPrimes(arr, N); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript Program to implement // the above approach let MAXN = 100001 let prime = new Array(MAXN).fill(true); // Function to find prime numbers using sieve function SieveOfEratosthenes() { let n = MAXN - 1; // Create a boolean array // "prime[0..n]" and initialize // all entries it as true. // A value in prime[i] will // finally be false if i is // Not a prime, else true. prime[0] = false; prime[1] = false; for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (let i = p * p; i <= n; i = i + p) prime[i] = false; } } } // Function to print the position and // value of the primes in given matrix function printPrimes(arr, n) { // Traverse the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // Check if the element is prime // or not in O(1) if (prime[arr[i][j]] == true) { // Print the position and value // if found true document.write((i + 1) + " " + (j + 1) + " " + (arr[i][j]) + "<br>"); } } } } // Driver Code let N = 2; let arr = new Array(N); let temp = [1, 2] arr[0] = temp; let temp1 = [2, 1] arr[1] = temp1; // Precomputing prime numbers using sieve SieveOfEratosthenes(); // Find and print prime numbers // present in the matrix printPrimes(arr, N); // This code is contributed by Potta Lokesh </script> |
Output
1 2 2 2 1 2
Time Complexity: O(N*M) where N*M is the size of matrix.
Auxiliary Space: O(maxNum) where maxNum is the largest element in the matrix.
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!
