Given a matrix of size N x M, the task is to print the elements of the row whose product has a maximum count of prime factors.
Examples:
Input: arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
Output: 7 8 9
Explanation:
Row 1: (1, 2, 3) has product 6 and it has 2 prime factors.
Row 2: (4, 5, 6) has product 120 and it has 3 prime factors.
Row 3: (7, 8, 9) has product 504 and it has 6 prime factors.
Therefore, the output is 7 8 9, as it has maximum count of prime factors.
Input: arr[][] = {{11, 12, 13}, {14, 15, 16}, {17, 18, 19}}
Output: 14 15 16
Approach:
- Find the number of overall occurrences of each prime factor in whole each row by traversing all elements and finding their prime factors. We use hashing to count occurrences.
- Let the counts of occurrences of prime factors be a1, a2, …aK. If we have K distinct prime factors, then the answer will be:
- Compare this with the value that stores the maximum count of prime factors in a row in max_factor. If greater, update the value of the row.
- Continue until all rows have been traversed.
Below is the implementation of the above approach:
C++
// C++ implementation to find the row // whose product has maximum number // of prime factors #include <bits/stdc++.h> using namespace std; #define N 3 #define M 5 int Large = 1e6; vector<int> prime; // function for SieveOfEratosthenes void SieveOfEratosthenes() { // Create a boolean array "isPrime[0..N]" // and initialize all entries it as true. // A value in isPrime[i] will finally be // false if i is not a prime, else true. bool isPrime[Large + 1]; memset(isPrime, true, sizeof(isPrime)); for (int p = 2; p * p <= Large; p++) { // check if isPrime[p] is not changed if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= Large; i += p) isPrime[i] = false; } } // Print all isPrime numbers for (int p = 2; p <= Large; p++) if (isPrime[p]) prime.push_back(p); } // function to display the answer void Display(int arr[][M], int row) { for (int i = 0; i < M; i++) cout << arr[row][i] << " "; } // function to Count the row number of // divisors in particular row multiplication void countDivisorsMult(int arr[][M]) { // Find count of occurrences // of each prime factor unordered_map<int, int> mp; int row_no = 0; long long max_factor = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int no = arr[i][j]; for (int k = 0; k < prime.size(); k++) { while (no > 1 && no % prime[k] == 0) { no /= prime[k]; mp[prime[k]]++; } if (no == 1) break; } } // Compute count of all divisors long long int res = 1; for (auto it : mp) { res *= (it.second + 1L); } // Update row number if // factors of this row is max if (max_factor < res) { row_no = i; max_factor = res; } // Clearing map to store // prime factors for next row mp.clear(); } Display(arr, row_no); } // Driver code int main() { int arr[N][M] = { { 1, 2, 3, 10, 23 }, { 4, 5, 6, 7, 8 }, { 7, 8, 9, 15, 45 } }; SieveOfEratosthenes(); countDivisorsMult(arr); return 0; } |
Java
// Java implementation to find the row // whose product has maximum number // of prime factors import java.util.*; class GFG{ static final int N = 3; static final int M = 5; static int Large = (int) 1e6; static Vector<Integer> prime = new Vector<Integer>(); // function for SieveOfEratosthenes static void SieveOfEratosthenes() { // Create a boolean array "isPrime[0..N]" // and initialize all entries it as true. // A value in isPrime[i] will finally be // false if i is not a prime, else true. boolean []isPrime = new boolean[Large + 1]; Arrays.fill(isPrime, true); for (int p = 2; p * p <= Large; p++) { // check if isPrime[p] is not changed if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= Large; i += p) isPrime[i] = false; } } // Print all isPrime numbers for (int p = 2; p <= Large; p++) if (isPrime[p]) prime.add(p); } // function to display the answer static void Display(int arr[][], int row) { for (int i = 0; i < M; i++) System.out.print(arr[row][i]+ " "); } // function to Count the row number of // divisors in particular row multiplication static void countDivisorsMult(int arr[][]) { // Find count of occurrences // of each prime factor HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); int row_no = 0; long max_factor = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int no = arr[i][j]; for (int k = 0; k < prime.size(); k++) { while (no > 1 && no % prime.get(k) == 0) { no /= prime.get(k); if(mp.containsKey(prime.get(k))) mp.put(prime.get(k), prime.get(k)+1); else mp.put(prime.get(k), 1); } if (no == 1) break; } } // Compute count of all divisors int res = 1; for (Map.Entry<Integer,Integer> it : mp.entrySet()) { res *= (it.getValue() + 1L); } // Update row number if // factors of this row is max if (max_factor < res) { row_no = i; max_factor = res; } // Clearing map to store // prime factors for next row mp.clear(); } Display(arr, row_no); } // Driver code public static void main(String[] args) { int arr[][] = { { 1, 2, 3, 10, 23 }, { 4, 5, 6, 7, 8 }, { 7, 8, 9, 15, 45 } }; SieveOfEratosthenes(); countDivisorsMult(arr); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find the row # whose product has maximum number # of prime factors N = 3M = 5 Large = int(1e6); prime = []; # function for SieveOfEratosthenes def SieveOfEratosthenes() : # Create a boolean array "isPrime[0..N]" # and initialize all entries it as true. # A value in isPrime[i] will finally be # false if i is not a prime, else true. isPrime = [True]*(Large + 1); for p in range(2, int(Large**(1/2))) : # check if isPrime[p] is not changed if (isPrime[p] == True) : # Update all multiples of p for i in range(p*2, Large + 1, p) : isPrime[i] = False; # Print all isPrime numbers for p in range(2, Large + 1) : if (isPrime[p]) : prime.append(p); # function to display the answer def Display(arr, row) : for i in range(M) : print(arr[row][i], end=" "); # function to Count the row number of # divisors in particular row multiplication def countDivisorsMult(arr) : # Find count of occurrences # of each prime factor mp = {}; row_no = 0;max_factor = 0; for i in range(N) : for j in range(M) : no = arr[i][j] for k in range(len(prime)) : while (no > 1 and no % prime[k] == 0) : no //= prime[k]; if prime[k] not in mp : mp[prime[k]] = 0 mp[prime[k]] += 1; if (no == 1) : break; # Compute count of all divisors res = 1; for it in mp : res *= mp[it]; # Update row number if # factors of this row is max if (max_factor < res) : row_no = i; max_factor = res; # Clearing map to store # prime factors for next row mp.clear(); Display(arr, row_no); # Driver code if __name__ == "__main__" : arr = [ [ 1, 2, 3, 10, 23 ], [ 4, 5, 6, 7, 8 ], [ 7, 8, 9, 15, 45 ] ]; SieveOfEratosthenes(); countDivisorsMult(arr); # This code is contributed by Yash_R |
C#
// C# implementation to find the row // whose product has maximum number // of prime factors using System; using System.Collections.Generic; class GFG{ static readonly int N = 3; static readonly int M = 5; static int Large = (int) 1e6; static List<int> prime = new List<int>(); // function for SieveOfEratosthenes static void SieveOfEratosthenes() { // Create a bool array "isPrime[0..N]" // and initialize all entries it as true. // A value in isPrime[i] will finally be // false if i is not a prime, else true. bool []isPrime = new bool[Large + 1]; for (int p = 0; p <= Large; p++) isPrime[p] = true; for (int p = 2; p * p <= Large; p++) { // check if isPrime[p] is not changed if (isPrime[p] == true) { // Update all multiples of p for (int i = p * 2; i <= Large; i += p) isPrime[i] = false; } } // Print all isPrime numbers for (int p = 2; p <= Large; p++) if (isPrime[p]) prime.Add(p); } // function to display the answer static void Display(int [, ]arr, int row) { for (int i = 0; i < M; i++) Console.Write(arr[row, i] + " "); } // function to Count the row number of // divisors in particular row multiplication static void countDivisorsMult(int [, ]arr) { // Find count of occurrences // of each prime factor Dictionary<int, int> mp = new Dictionary<int, int>(); int row_no = 0; long max_factor = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int no = arr[i,j]; for (int k = 0; k < prime.Count; k++) { while (no > 1 && no % prime[k] == 0) { no /= prime[k]; if(mp.ContainsKey(prime[k])) mp[prime[k]] = prime[k] + 1; else mp.Add(prime[k], 1); } if (no == 1) break; } } // Compute count of all divisors int res = 1; foreach (KeyValuePair<int,int> it in mp) { res *= (it.Value + 1); } // Update row number if // factors of this row is max if (max_factor < res) { row_no = i; max_factor = res; } // Clearing map to store // prime factors for next row mp.Clear(); } Display(arr, row_no); } // Driver code public static void Main(String[] args) { int [, ]arr = {{1, 2, 3, 10, 23}, {4, 5, 6, 7, 8}, {7, 8, 9, 15, 45}}; SieveOfEratosthenes(); countDivisorsMult(arr); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to find the row // whose product has maximum number // of prime factors let N = 3 let M = 5 let Large = 1e6; let prime = new Array(); // function for SieveOfEratosthenes function SieveOfEratosthenes() { // Create a boolean array "isPrime[0..N]" // and initialize all entries it as true. // A value in isPrime[i] will finally be // false if i is not a prime, else true. let isPrime = new Array(); for(let i = 0; i < Large + 1; i++){ isPrime.push([]) } isPrime.fill(true); for (let p = 2; p * p <= Large; p++) { // check if isPrime[p] is not changed if (isPrime[p] == true) { // Update all multiples of p for (let i = p * 2; i <= Large; i += p) isPrime[i] = false; } } // Print all isPrime numbers for (let p = 2; p <= Large; p++) if (isPrime[p]) prime.push(p); } // function to display the answer function Display(arr, row) { for (let i = 0; i < M; i++) document.write(arr[row][i] + " "); } // function to Count the row number of // divisors in particular row multiplication function countDivisorsMult(arr) { // Find count of occurrences // of each prime factor let mp = new Map(); let row_no = 0; let max_factor = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { let no = arr[i][j]; for (let k = 0; k < prime.length; k++) { while (no > 1 && no % prime[k] == 0) { no /= prime[k]; if(mp.has(prime[k])){ mp.set(prime[k], mp.get(prime[k]) + 1) }else{ mp.set(prime[k], 1) } } if (no == 1) break; } } // Compute count of all divisors let res = 1; for (let it of mp) { res *= (it[1] + 1); } // Update row number if // factors of this row is max if (max_factor < res) { row_no = i; max_factor = res; } // Clearing map to store // prime factors for next row mp.clear(); } Display(arr, row_no); } // Driver code let arr = [ [ 1, 2, 3, 10, 23 ], [ 4, 5, 6, 7, 8 ], [ 7, 8, 9, 15, 45 ] ]; SieveOfEratosthenes(); countDivisorsMult(arr); // This code is contributed by gfgking </script> |
Output:
7 8 9 15 45
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!
