Given an array arr[] of size N, the task is to find the maximum sum possible of the count of distinct prime factors of K array elements.
Examples:
Input: arr[] = {6, 9, 12}, K = 2
Output: 4
Explanation:
Distinct prime factors of 6, 9, 12 are 2, 1, 2.
K elements whose distinct prime factors are maximum are 6 and 12. Therefore, sum of their count = 2 + 2 = 4.Input: arr[] = {4, 8, 10, 6}, K = 3
Output: 5
Explanation:
Distinct prime factors of 4, 8, 10, 6 are 1, 1, 2, 2.
K elements whose distinct prime factors are maximum are 4, 6, 10. Therefore, sum of their count = 1 + 2 + 2 = 5.
Approach: Follow the steps below to solve the problem:
- Initialize a boolean array prime[] of size 106 to store whether the number is prime or not by Sieve of Eratosthenes technique.
- Initialize an array CountDistinct[] to store the number of distinct prime factors of numbers.
- Increment the count of prime factors in its multiples, while marking the number as prime.
- Maximum number of distinct prime numbers of a number less than 106 is 8 i.e, (2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 9699690 > 106).
- Initialize a variable, say sum to store the maximum sum of distinct prime factors of K array elements.
- Initialize an array PrimeFactor[] of size 20 to store the count of all distinct prime factors and initialize it to 0.
- Now traverse the array arr[] and increment PrimeFactor[CountDistinct[arr[i]]]++.
- Traverse the array PrimeFactor[] from backward and increment sum up to K times till it becomes 0.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAX 1000000// Function to find the maximum sum of count// of distinct prime factors of K array elementsint maxSumOfDistinctPrimeFactors(int arr[], int N, int K){ // Stores the count of distinct primes int CountDistinct[MAX + 1]; // Stores 1 and 0 at prime and // non-prime indices respectively bool prime[MAX + 1]; // Initialize the count of factors to 0 for (int i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (long long int i = 2; i <= MAX; i++) { if (prime[i] == true) { // Count of factors of a // prime number is 1 CountDistinct[i] = 1; for (long long int j = i * 2; j <= MAX; j += i) { // Increment CountDistinct // of all multiples of i CountDistinct[j]++; // Mark its multiples non-prime prime[j] = false; } } } // Stores the maximum sum of distinct // prime factors of K array elements int sum = 0; // Stores the count of all distinct // prime factors int PrimeFactor[20] = { 0 }; // Traverse the array to find // count of all array elements for (int i = 0; i < N; i++) { PrimeFactor[CountDistinct[arr[i]]]++; } // Maximum sum of K prime factors // of array elements for (int i = 19; i >= 1; i--) { // Check for the largest prime factor while (PrimeFactor[i] > 0) { // Increment sum sum += i; // Decrement its count and K PrimeFactor[i]--; K--; if (K == 0) break; } if (K == 0) break; } // Print the maximum sum cout << sum;}// Driver codeint main(){ // Given array int arr[] = { 6, 9, 12 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Given value of K int K = 2; maxSumOfDistinctPrimeFactors(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ public static int MAX = 1000000; // Function to find the maximum sum of count // of distinct prime factors of K array elements static void maxSumOfDistinctPrimeFactors(int[] arr, int N, int K) { // Stores the count of distinct primes int[] CountDistinct = new int[MAX + 1]; // Stores 1 and 0 at prime and // non-prime indices respectively boolean[] prime = new boolean[MAX + 1]; // Initialize the count of factors to 0 for (int i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (int i = 2; i <= MAX; i++) { if (prime[i] == true) { // Count of factors of a // prime number is 1 CountDistinct[i] = 1; for (int j = i * 2; j <= MAX; j += i) { // Increment CountDistinct // of all multiples of i CountDistinct[j]++; // Mark its multiples non-prime prime[j] = false; } } } // Stores the maximum sum of distinct // prime factors of K array elements int sum = 0; // Stores the count of all distinct // prime factors int[] PrimeFactor = new int[20]; // Traverse the array to find // count of all array elements for (int i = 0; i < N; i++) { PrimeFactor[CountDistinct[arr[i]]]++; } // Maximum sum of K prime factors // of array elements for (int i = 19; i >= 1; i--) { // Check for the largest prime factor while (PrimeFactor[i] > 0) { // Increment sum sum += i; // Decrement its count and K PrimeFactor[i]--; K--; if (K == 0) break; } if (K == 0) break; } // Print the maximum sum System.out.print(sum); } // Driver code public static void main(String[] args) { // Given array int[] arr = { 6, 9, 12 }; // Size of the array int N = arr.length; // Given value of K int K = 2; maxSumOfDistinctPrimeFactors(arr, N, K); }}// This code is contributed by Dharanendra L V. |
Python3
# Python 3 program for the above approachMAX = 1000000# Function to find the maximum sum of count# of distinct prime factors of K array elementsdef maxSumOfDistinctPrimeFactors(arr, N, K): # Stores the count of distinct primes CountDistinct = [0]*(MAX + 1) # Stores 1 and 0 at prime and # non-prime indices respectively prime = [False]*(MAX + 1) # Initialize the count of factors to 0 for i in range(MAX + 1): CountDistinct[i] = 0 prime[i] = True # Sieve of Eratosthenes for i in range(2, MAX + 1): if (prime[i] == True): # Count of factors of a # prime number is 1 CountDistinct[i] = 1 for j in range(i * 2, MAX + 1, i): # Increment CountDistinct # of all multiples of i CountDistinct[j] += 1 # Mark its multiples non-prime prime[j] = False # Stores the maximum sum of distinct # prime factors of K array elements sum = 0 # Stores the count of all distinct # prime factors PrimeFactor = [0]*20 # Traverse the array to find # count of all array elements for i in range(N): PrimeFactor[CountDistinct[arr[i]]] += 1 # Maximum sum of K prime factors # of array elements for i in range(19, 0, -1): # Check for the largest prime factor while (PrimeFactor[i] > 0): # Increment sum sum += i # Decrement its count and K PrimeFactor[i] -= 1 K -= 1 if (K == 0): break if (K == 0): break # Print the maximum sum print(sum)# Driver codeif __name__ == "__main__": # Given array arr = [6, 9, 12] # Size of the array N = len(arr) # Given value of K K = 2 maxSumOfDistinctPrimeFactors(arr, N, K) # This code is contributed by chitranayal. |
C#
using System;public class GFG { public static int MAX = 1000000; // Function to find the maximum sum of count // of distinct prime factors of K array elements static void maxSumOfDistinctPrimeFactors(int[] arr, int N, int K) { // Stores the count of distinct primes int[] CountDistinct = new int[MAX + 1]; // Stores 1 and 0 at prime and // non-prime indices respectively bool [] prime = new bool[MAX + 1]; // Initialize the count of factors to 0 for (int i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (int i = 2; i <= MAX; i++) { if (prime[i] == true) { // Count of factors of a // prime number is 1 CountDistinct[i] = 1; for (int j = i * 2; j <= MAX; j += i) { // Increment CountDistinct // of all multiples of i CountDistinct[j]++; // Mark its multiples non-prime prime[j] = false; } } } // Stores the maximum sum of distinct // prime factors of K array elements int sum = 0; // Stores the count of all distinct // prime factors int[] PrimeFactor = new int[20]; // Traverse the array to find // count of all array elements for (int i = 0; i < N; i++) { PrimeFactor[CountDistinct[arr[i]]]++; } // Maximum sum of K prime factors // of array elements for (int i = 19; i >= 1; i--) { // Check for the largest prime factor while (PrimeFactor[i] > 0) { // Increment sum sum += i; // Decrement its count and K PrimeFactor[i]--; K--; if (K == 0) break; } if (K == 0) break; } // Print the maximum sum Console.Write(sum); } // Driver code static public void Main() { // Given array int[] arr = { 6, 9, 12 }; // Size of the array int N = arr.Length; // Given value of K int K = 2; maxSumOfDistinctPrimeFactors(arr, N, K); }}// This code is contributed by Dharanendra L V. |
Javascript
<script>// JavaScript program of the above approachlet MAX = 1000000; // Function to find the maximum sum of count // of distinct prime factors of K array elements function maxSumOfDistinctPrimeFactors( arr, N, K) { // Stores the count of distinct primes let CountDistinct = []; for (let i = 0; i <= MAX ; i++) { CountDistinct[i] = 0; } // Stores 1 and 0 at prime and // non-prime indices respectively let prime = []; for (let i = 0; i <= MAX ; i++) { prime[i] = 0; } // Initialize the count of factors to 0 for (let i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (let i = 2; i <= MAX; i++) { if (prime[i] == true) { // Count of factors of a // prime number is 1 CountDistinct[i] = 1; for (let j = i * 2; j <= MAX; j += i) { // Increment CountDistinct // of all multiples of i CountDistinct[j]++; // Mark its multiples non-prime prime[j] = false; } } } // Stores the maximum sum of distinct // prime factors of K array elements let sum = 0; // Stores the count of all distinct // prime factors let PrimeFactor = []; for (let i = 0; i <= 20 ; i++) { PrimeFactor[i] = 0; } // Traverse the array to find // count of all array elements for (let i = 0; i < N; i++) { PrimeFactor[CountDistinct[arr[i]]]++; } // Maximum sum of K prime factors // of array elements for (let i = 19; i >= 1; i--) { // Check for the largest prime factor while (PrimeFactor[i] > 0) { // Increment sum sum += i; // Decrement its count and K PrimeFactor[i]--; K--; if (K == 0) break; } if (K == 0) break; } // Print the maximum sum document.write(sum); } // Driver Code // Given array let arr = [ 6, 9, 12 ]; // Size of the array let N = arr.length; // Given value of K let K = 2; maxSumOfDistinctPrimeFactors(arr, N, K);</script> |
Output:
4
Time Complexity: O(N * log(log(N)))
Auxiliary Space: O(MAX)
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!
