Maximizar la suma del conteo de distintos factores primos de K elementos de array

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *