Given an array arr[] of N positive integers and an integer K., The task is to create a set of prime numbers such that the sum of all the powers of prime numbers in the prime factorization of all the array elements is divisible by K.
Examples:
Input: arr[] = {1, 2, 3}, K = 1
Output: {2, 3}
Explanation:
2 = 21
3 = 31
The power of 2 is 1 which is divisible by K(=1).
The power of 2 is 1 which is divisible by K(=1).Input: arr[] = {2, 2, 4, 8}, K = 10
Output: {}
Explanation:
2 = 21
2 = 21
4 = 22
8 = 23
The power of 2 is (1 + 1 + 2 + 3) = 7 which is not divisible by K(=10).
Thus, the output empty set.
Naive approach: The idea is to find all prime numbers less than or equal to the maximum element of the array arr[]. For each prime number count number of times, it divides the array element. If the value of count is divisible by K, then insert the prime number into the resultant set. At the end print elements of the set.
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach the idea is to precompute the count of all the prime factors of all the numbers. Below are the steps:
- Create the smallest prime factorization array spf[] up to the maximum number in the array. This step is used to precalculate the prime factors of a number.
- Traverse the given array arr[] and for each element find the sum of all the count of factors stored in spf[] array.
- For each sum of the power of a prime number in the above steps stored it frequency in a Map.
- Traverse the map if, for any number, frequency is divisible by K then store that number.
- Finally, print all the numbers stored in the above step.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <unordered_map> #include <vector> using namespace std; // To store the smallest prime // factor till 10^5 int spf[10001]; // Function to compute smallest // prime factor array void spf_array(int spf[]) { // Initialize the spf array // first element spf[1] = 1; for (int i = 2; i < 1000; i++) // Marking smallest prime // factor for every number // to be itself spf[i] = i; // Separately marking smallest // prime factor for every even // number as 2 for (int i = 4; i < 1000; i += 2) spf[i] = 2; for (int i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all // numbers divisible by i for (int j = i * i; j < 1000; j += i) // Marking spf[j] if it is // not previously marked if (spf[j] == j) spf[j] = i; } } } // Function that finds minimum operation void frequent_prime(int arr[], int N, int K) { // Create a spf[] array spf_array(spf); // Map created to store the // unique prime numbers unordered_map<int, int> Hmap; // To store the result vector<int> result; int i = 0; // To store minimum operations int c = 0; // To store every unique // prime number for (i = 0; i < N; i++) { int x = arr[i]; while (x != 1) { Hmap[spf[x]] = Hmap[spf[x]] + 1; x = x / spf[x]; } } // Erase 1 as a key because // it is not a prime number Hmap.erase(1); for (auto x : Hmap) { // First Prime Number int primeNum = x.first; int frequency = x.second; // Frequency is divisible // by K then insert primeNum // in the result[] if (frequency % K == 0) { result.push_back(primeNum); } } // Print the elements // if it exists if (result.size() > 0) { for (auto& it : result) { cout << it << ' '; } } else { cout << "{}"; } } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 4, 6 }; // Given K int K = 1; int N = sizeof(arr) / sizeof(arr[0]); // Function Call frequent_prime(arr, N, K); } |
Java
// Java program for the above approach import java.util.*;class GFG{ // To store the smallest prime// factor till 10^5static int[] spf = new int[10001];// Function to compute smallest// prime factor arraystatic void spf_array(int spf[]){ // Initialize the spf array // first element spf[1] = 1; for(int i = 2; i < 1000; i++) // Marking smallest prime // factor for every number // to be itself spf[i] = i; // Separately marking smallest // prime factor for every even // number as 2 for(int i = 4; i < 1000; i += 2) spf[i] = 2; for(int i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all // numbers divisible by i for(int j = i * i; j < 1000; j += i) // Marking spf[j] if it is // not previously marked if (spf[j] == j) spf[j] = i; } }}// Function that finds minimum operationstatic void frequent_prime(int arr[], int N, int K){ // Create a spf[] array spf_array(spf); // Map created to store the // unique prime numbers Map<Integer, Integer> Hmap = new TreeMap<>(); // To store the result ArrayList<Integer> result = new ArrayList<>(); int i = 0; // To store minimum operations int c = 0; // To store every unique // prime number for(i = 0; i < N; i++) { int x = arr[i]; while (x != 1) { Hmap.put(spf[x], Hmap.getOrDefault(spf[x], 0) + 1); x = x / spf[x]; } } // Erase 1 as a key because // it is not a prime number Hmap.remove(1); for(Map.Entry<Integer, Integer> x : Hmap.entrySet()) { // First prime number int primeNum = x.getKey(); int frequency = x.getValue(); // Frequency is divisible // by K then insert primeNum // in the result[] if (frequency % K == 0) { result.add(primeNum); } } // Print the elements // if it exists if (result.size() > 0) { for(Integer it : result) { System.out.print(it + " "); } } else { System.out.print("{}"); }}// Driver codepublic static void main (String[] args){ // Given array arr[] int arr[] = { 1, 4, 6 }; // Given K int K = 1; int N = arr.length; // Function call frequent_prime(arr, N, K);}}// This code is contributed by offbeat |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // To store the smallest prime // factor till 10^5 static int[] spf = new int[10001]; // Function to compute smallest // prime factor array static void spf_array(int[] spf) { // Initialize the spf array // first element spf[1] = 1; for (int i = 2; i < 1000; i++) // Marking smallest prime // factor for every number // to be itself spf[i] = i; // Separately marking smallest // prime factor for every even // number as 2 for (int i = 4; i < 1000; i += 2) spf[i] = 2; for (int i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all // numbers divisible by i for (int j = i * i; j < 1000; j += i) // Marking spf[j] if it is // not previously marked if (spf[j] == j) spf[j] = i; } } } // Function that finds minimum operation static void frequent_prime(int[] arr, int N, int K) { // Create a spf[] array spf_array(spf); // Map created to store the // unique prime numbers SortedDictionary<int, int> Hmap = new SortedDictionary<int, int>(); // To store the result List<int> result = new List<int>(); int i = 0; // To store every unique // prime number for (i = 0; i < N; i++) { int x = arr[i]; while (x != 1) { if (Hmap.ContainsKey(spf[x])) Hmap[spf[x]] = spf[x] + 1; else Hmap.Add(spf[x], 1); x = x / spf[x]; } } // Erase 1 as a key because // it is not a prime number Hmap.Remove(1); foreach(KeyValuePair<int, int> x in Hmap) { // First prime number int primeNum = x.Key; int frequency = x.Value; // Frequency is divisible // by K then insert primeNum // in the result[] if (frequency % K == 0) { result.Add(primeNum); } } // Print the elements // if it exists if (result.Count > 0) { foreach(int it in result) { Console.Write(it + " "); } } else { Console.Write("{}"); } } // Driver code public static void Main(String[] args) { // Given array []arr int[] arr = {1, 4, 6}; // Given K int K = 1; int N = arr.Length; // Function call frequent_prime(arr, N, K); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # To store the smallest prime # factor till 10^5 spf = [0 for i in range(10001)] # Function to compute smallest # prime factor array def spf_array(spf): # Initialize the spf array # first element spf[1] = 1 for i in range(2, 1000, 1): # Marking smallest prime # factor for every number # to be itself spf[i] = i # Separately marking smallest # prime factor for every even # number as 2 for i in range(4, 1000, 2): spf[i] = 2 i = 3 while( i* i < 1000): # Checking if i is prime if (spf[i] == i): # Marking SPF for all # numbers divisible by i j = i * i while(j < 1000): # Marking spf[j] if it is # not previously marked if (spf[j] == j): spf[j] = i j += i i += 1# Function that finds minimum operation def frequent_prime(arr, N, K): # Create a spf[] array spf_array(spf) # Map created to store the # unique prime numbers Hmap = {} # To store the result result = [] i = 0 # To store minimum operations c = 0 # To store every unique # prime number for i in range(N): x = arr[i] while (x != 1): Hmap[spf[x]] = Hmap.get(spf[x], 0) + 1 x = x // spf[x] # Erase 1 as a key because # it is not a prime number if (1 in Hmap): Hmap.pop(1) for key, value in Hmap.items(): # First Prime Number primeNum = key frequency = value # Frequency is divisible # by K then insert primeNum # in the result[] if (frequency % K == 0): result.append(primeNum) # Print the elements # if it exists result = result[::-1] if (len(result) > 0): for it in result: print(it, end = " ") else: print("{}")# Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 1, 4, 6 ] # Given K K = 1 N = len(arr) # Function Call frequent_prime(arr, N, K)# This code is contributed by ipg2016107 |
Javascript
<script>// JavaScript program for the above approach // To store the smallest prime // factor till 10^5 var spf = Array(10001);// Function to compute smallest // prime factor array function spf_array(spf) { // Initialize the spf array // first element spf[1] = 1; for (var i = 2; i < 1000; i++) // Marking smallest prime // factor for every number // to be itself spf[i] = i; // Separately marking smallest // prime factor for every even // number as 2 for (var i = 4; i < 1000; i += 2) spf[i] = 2; for (var i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all // numbers divisible by i for (var j = i * i; j < 1000; j += i) // Marking spf[j] if it is // not previously marked if (spf[j] == j) spf[j] = i; } } } // Function that finds minimum operation function frequent_prime(arr, N, K) { // Create a spf[] array spf_array(spf); // Map created to store the // unique prime numbers var Hmap = new Map(); // To store the result var result = []; var i = 0; // To store minimum operations var c = 0; // To store every unique // prime number for (i = 0; i < N; i++) { var x = arr[i]; while (x != 1) { if(Hmap.has(spf[x])) Hmap.set(spf[x], Hmap.get(spf[x])+1) else Hmap.set(spf[x], 1); x = parseInt(x / spf[x]); } } // Erase 1 as a key because // it is not a prime number Hmap.delete(1); Hmap.forEach((value, key) => { // First Prime Number var primeNum = key; var frequency = value; // Frequency is divisible // by K then insert primeNum // in the result[] if (frequency % K == 0) { result.push(primeNum); } }); // Print the elements // if it exists if (result.length > 0) { result.forEach(it => { document.write(it+" "); }); } else { document.write( "{}"); } } // Driver Code // Given array arr[] var arr = [1, 4, 6]; // Given K var K = 1; var N = arr.length; // Function Call frequent_prime(arr, N, K); </script> |
Output:
3 2
Time Complexity: O(M*log(M)), where M is the maximum element of the array.
Auxiliary Space: O(M)
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!
