Dada una array arr[] de tamaño N , la tarea es encontrar la suma máxima posible del recuento de distintos factores primos de K elementos de la array.
Ejemplos:
Entrada: arr[] = {6, 9, 12}, K = 2
Salida: 4
Explicación:
Los factores primos distintos de 6, 9, 12 son 2, 1, 2.
K elementos cuyos factores primos distintos son máximos son 6 y 12 Por lo tanto, la suma de sus cuentas = 2 + 2 = 4.Entrada: arr[] = {4, 8, 10, 6}, K = 3
Salida: 5
Explicación:
Los factores primos distintos de 4, 8, 10, 6 son 1, 1, 2, 2.
K elementos cuyos factores primos distintos son máximos son 4, 6, 10. Por lo tanto, la suma de su cuenta = 1 + 2 + 2 = 5.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array booleana prime[] de tamaño 10 6 para almacenar si el número es primo o no mediante la técnica de la criba de Eratóstenes .
- Inicialice una array CountDistinct[] para almacenar el número de factores primos distintos de números.
- Incrementa el conteo de factores primos en sus múltiplos, mientras marcas el número como primo.
- El número máximo de números primos distintos de un número menor que 10 6 es 8, es decir, (2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 = 9699690 > 10 6 ).
- Inicialice una variable, digamos sum para almacenar la suma máxima de distintos factores primos de K elementos de array.
- Inicialice una array PrimeFactor[] de tamaño 20 para almacenar el recuento de todos los factores primos distintos e inicialícelo en 0 .
- Ahora recorra la array arr[] e incremente PrimeFactor[CountDistinct[arr[i]]]++.
- Recorra la array PrimeFactor[] desde atrás e incremente la suma hasta K veces hasta que se convierta en 0.
A continuación se muestra la implementación del enfoque anterior:
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 elements
int 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 code
int 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 approach
import 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 approach MAX = 1000000 # Function to find the maximum sum of count # of distinct prime factors of K array elements def 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 code if __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 approach
let 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>
Producción:
4
Complejidad de tiempo: O(N * log(log(N)))
Espacio auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA