Cuente los elementos de la array que tienen exactamente K divisores

Dada una array arr[] que consta de N enteros y un entero K , la tarea es contar el número de elementos de la array que tienen exactamente K divisores.

Ejemplos:

Entrada: N = 5, arr[] = { 3, 6, 2, 9, 4 }, K = 2
Salida: 2
Explicación: arr[0] (= 3) y arr[2] (= 2) tienen exactamente 2 divisores

Entrada: N = 5, arr[] = { 3, 6, 2, 9, 4 }, K = 3
Salida: 2
Explicación: arr[3] (= 9) y arr[4] (= 4) tienen exactamente 3 divisores

Enfoque: La idea para resolver este problema es calcular el número total de divisores de cada elemento del arreglo y almacenarlos en un Map . Luego, recorra la array y para cada elemento de la array, verifique si tiene exactamente K divisores. Imprime el recuento de dichos números. Siga los pasos a continuación para resolver el problema:

donde a i son factores primos y p i son potencias integrales a las que están elevados.

  • Cuente el número total de divisores de cada elemento del arreglo usando la siguiente fórmula:

  • Inicialice un mapa para almacenar el número total de divisores de cada elemento de array.
  • Recorra la array e inicialice una variable, por ejemplo, count , para contar el número de elementos que tienen exactamente K número total de divisores.
  • Imprime el número de elementos que tienen exactamente K divisores.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores prime numbers
// using Sieve of Eratosthenes
bool prime[100000];
 
// Function to find the maximum element
int maximumElement(int arr[], int N)
{
  // Stores the maximum element
  // of the array
  int max = arr[0];
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
 
    // If current element
    // is maximum so far
    if (max < arr[i]) {
 
      // Update maximum
      max = arr[i];
    }
  }
 
  // Return maximum element
  return max;
}
 
// Function to find the prime numbers
// using sieve of eratosthenes algorithm
void sieveOfEratosthenes(int max)
{
  // Calculate primes using Sieve
  memset(prime, true, max+1);
 
  for (int p = 2; p * p < max; p++)
 
    // If current element is prime
    if (prime[p] == true)
 
      // Make all multiples non-prime
      for (int i = p * 2; i < max; i += p)
        prime[i] = false;
}
 
// Function to count divisors of n
int divCount(int n)
{
 
  // Traversing through
  // all prime numbers
  int total = 1;
  for (int p = 2; p <= n; p++) {
 
    // If it is a prime number
    if (prime[p]) {
 
      // Calculate number of divisors
      // with the formula
      // number of divisors = (p1 + 1) * (p2 + 1)
      // *.....* (pn + 1)
      // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn)
      // ai: prime divisor of n
      // pi: power in factorization
      int count = 0;
 
      if (n % p == 0) {
 
        while (n % p == 0) {
          n = n / p;
          count++;
        }
        total = total * (count + 1);
      }
    }
  }
 
  // Return the total number of divisors
  return total;
}
 
// Function to count array elements
// having exactly K divisors
int countElements(int arr[], int N, int K)
{
 
  // Initialize a map to store
  // count of divisors of array elements
  map<int, int> map;
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
 
    // If element is not already present in
    // the Map, then insert it into the Map
    if (map.find(arr[i]) == map.end()) {
      // Function call to count the total
      // number of divisors
      map.insert({arr[i], divCount(arr[i])});
    }
  }
 
  // Stores the number of
  // elements with divisor K
  int count = 0;
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
 
    // If current element
    // has exactly K divisors
    if (map.at(arr[i]) == K) {
      count++;
    }
  }
 
  // Return the number of
  // elements having K divisors
  return count;
}
 
// Driver Code
int main()
{
 
  int arr[] = { 3, 6, 2, 9, 4 };
  int N = sizeof(arr) / sizeof(arr[0]);
  int K = 2;
 
  // Find the maximum element
  int max = maximumElement(arr, N);
 
  // Generate all prime numbers
  sieveOfEratosthenes(max);
 
  cout << countElements(arr, N, K);
 
  return 0;
}
 
// This code is contributed by Dharanendra L V

Java

// Java program for the above approach
import java.util.*;
class GFG {
 
    // Stores prime numbers
    // using Sieve of Eratosthenes
    public static boolean prime[];
 
    // Function to find the maximum element
    public static int maximumElement(
        int arr[], int N)
    {
        // Stores the maximum element
        // of the array
        int max = arr[0];
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // If current element
            // is maximum so far
            if (max < arr[i]) {
 
                // Update maximum
                max = arr[i];
            }
        }
 
        // Return maximum element
        return max;
    }
 
    // Function to find the prime numbers
    // using sieve of eratosthenes algorithm
    public static void sieveOfEratosthenes(int max)
    {
        // Initialize primes having
        // size of maximum element + 1
        prime = new boolean[max + 1];
 
        // Calculate primes using Sieve
        Arrays.fill(prime, true);
 
        for (int p = 2; p * p < max; p++)
 
            // If current element is prime
            if (prime[p] == true)
 
                // Make all multiples non-prime
                for (int i = p * 2; i < max; i += p)
                    prime[i] = false;
    }
 
    // Function to count divisors of n
    public static int divCount(int n)
    {
 
        // Traversing through
        // all prime numbers
        int total = 1;
        for (int p = 2; p <= n; p++) {
 
            // If it is a prime number
            if (prime[p]) {
 
                // Calculate number of divisors
                // with the formula
                // number of divisors = (p1 + 1) * (p2 + 1)
                // *.....* (pn + 1)
                // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn)
                // ai: prime divisor of n
                // pi: power in factorization
                int count = 0;
 
                if (n % p == 0) {
 
                    while (n % p == 0) {
                        n = n / p;
                        count++;
                    }
                    total = total * (count + 1);
                }
            }
        }
 
        // Return the total number of divisors
        return total;
    }
 
    // Function to count array elements
    // having exactly K divisors
    public static int countElements(
        int arr[], int N, int K)
    {
 
        // Initialize a map to store
        // count of divisors of array elements
        Map<Integer, Integer> map
            = new HashMap<Integer, Integer>();
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // If element is not already present in
            // the Map, then insert it into the Map
            if (!map.containsKey(arr[i])) {
                // Function call to count the total
                // number of divisors
                map.put(arr[i], divCount(arr[i]));
            }
        }
 
        // Stores the number of
        // elements with divisor K
        int count = 0;
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // If current element
            // has exactly K divisors
            if (map.get(arr[i]) == K) {
                count++;
            }
        }
 
        // Return the number of
        // elements having K divisors
        return count;
    }
 
    // Driver Code
    public static void main(
        String[] args)
    {
        int arr[] = { 3, 6, 2, 9, 4 };
        int N = arr.length;
        int K= 2;
 
        // Find the maximum element
        int max = maximumElement(arr, N);
 
        // Generate all prime numbers
        sieveOfEratosthenes(max);
 
        System.out.println(countElements(arr, N, K));
    }
}

Python3

# Python3 program for the above approach
 
# Stores prime numbers
# using Sieve of Eratosthenes
 
# Function to find the maximum element
def maximumElement(arr, N):
   
    # Stores the maximum element
    # of the array
    max = arr[0]
 
    # Traverse the array
    for i in range(N):
 
        # If current element
        # is maximum so far
        if (max < arr[i]):
 
            # Update maximum
            max = arr[i]
 
    # Return maximum element
    return max
 
# Function to find the prime numbers
# using sieve of eratosthenes algorithm
def sieveOfEratosthenes(max):
    global prime
    for p in range(2, max + 1):
        if p * p > max:
            break
 
        # If current element is prime
        if (prime[p] == True):
 
            # Make all multiples non-prime
            for i in range(2 * p, max, p):
                prime[i] = False
    return prime
 
# Function to count divisors of n
def divCount(n):
 
    # Traversing through
    # all prime numbers
    total = 1
    for p in range(2, n + 1):
 
        # If it is a prime number
        if (prime[p]):
 
            # Calculate number of divisors
            # with the formula
            # number of divisors = (p1 + 1) * (p2 + 1)
            # *.....* (pn + 1)
            # n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn)
            # ai: prime divisor of n
            # pi: power in factorization
            count = 0
 
            if (n % p == 0):
                while (n % p == 0):
                    n = n // p
                    count += 1
                total = total * (count + 1)
 
    # Return the total number of divisors
    return total
 
# Function to count array elements
# having exactly K divisors
def countElements(arr, N, K):
 
    # Initialize a map to store
    # count of divisors of array elements
    mp = {}
 
    # Traverse the array
    for i in range(N):
 
        # If element is not already present in
        # the Map, then insert it into the Map
        if (arr[i] not in mp):
             
            # Function call to count the total
            # number of divisors
            mp[arr[i]] = divCount(arr[i])
 
    # Stores the number of
    # elements with divisor K
    count = 0
 
    # Traverse the array
    for i in range(N):
 
        # If current element
        # has exactly K divisors
        if (mp[arr[i]] == K):
            count += 1
 
    # Return the number of
    # elements having K divisors
    return count
 
# Driver Code
if __name__ == '__main__':
    prime = [True for i in range(10**6)]
    arr = [3, 6, 2, 9, 4]
    N = len(arr)
    K= 2
 
    # Find the maximum element
    max = maximumElement(arr, N)
 
    # Generate all prime numbers
    prime = sieveOfEratosthenes(max)
    print(countElements(arr, N, K))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
    // Stores prime numbers
    // using Sieve of Eratosthenes
    public static bool []prime;
 
    // Function to find the maximum element
    public static int maximumElement(
        int []arr, int N)
    {
       
        // Stores the maximum element
        // of the array
        int max = arr[0];
 
        // Traverse the array
        for (int i = 0; i < N; i++)
        {
 
            // If current element
            // is maximum so far
            if (max < arr[i])
            {
 
                // Update maximum
                max = arr[i];
            }
        }
 
        // Return maximum element
        return max;
    }
 
    // Function to find the prime numbers
    // using sieve of eratosthenes algorithm
    public static void sieveOfEratosthenes(int max)
    {
       
        // Initialize primes having
        // size of maximum element + 1
        prime = new bool[max + 1];
 
        // Calculate primes using Sieve
        for (int i = 0; i < prime.Length; i++)
        prime[i] = true;
        for (int p = 2; p * p < max; p++)
 
            // If current element is prime
            if (prime[p] == true)
 
                // Make all multiples non-prime
                for (int i = p * 2; i < max; i += p)
                    prime[i] = false;
    }
 
    // Function to count divisors of n
    public static int divCount(int n)
    {
 
        // Traversing through
        // all prime numbers
        int total = 1;
        for (int p = 2; p <= n; p++)
        {
 
            // If it is a prime number
            if (prime[p])
            {
 
                // Calculate number of divisors
                // with the formula
                // number of divisors = (p1 + 1) * (p2 + 1)
                // *.....* (pn + 1)
                // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn)
                // ai: prime divisor of n
                // pi: power in factorization
                int count = 0;
                if (n % p == 0)
                {
                    while (n % p == 0)
                    {
                        n = n / p;
                        count++;
                    }
                    total = total * (count + 1);
                }
            }
        }
 
        // Return the total number of divisors
        return total;
    }
 
    // Function to count array elements
    // having exactly K divisors
    public static int countElements(int []arr,
                                    int N, int K)
    {
 
        // Initialize a map to store
        // count of divisors of array elements
        Dictionary<int, int> map
            = new Dictionary<int, int>();
 
        // Traverse the array
        for (int i = 0; i < N; i++)
        {
 
            // If element is not already present in
            // the Map, then insert it into the Map
            if (!map.ContainsKey(arr[i]))
            {
               
                // Function call to count the total
                // number of divisors
                map.Add(arr[i], divCount(arr[i]));
            }
        }
 
        // Stores the number of
        // elements with divisor K
        int count = 0;
 
        // Traverse the array
        for (int i = 0; i < N; i++)
        {
 
            // If current element
            // has exactly K divisors
            if (map[arr[i]] == K)
            {
                count++;
            }
        }
 
        // Return the number of
        // elements having K divisors
        return count;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int []arr = {3, 6, 2, 9, 4};
        int N = arr.Length;
        int K= 2;
 
        // Find the maximum element
        int max = maximumElement(arr, N);
 
        // Generate all prime numbers
        sieveOfEratosthenes(max);
        Console.WriteLine(countElements(arr, N, K));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
 
// Stores prime numbers
// using Sieve of Eratosthenes
let prime = new Array(100000);
 
// Function to find the maximum element
function maximumElement(arr, N)
{
// Stores the maximum element
// of the array
let max = arr[0];
 
// Traverse the array
for (let i = 0; i < N; i++) {
 
    // If current element
    // is maximum so far
    if (max < arr[i]) {
 
    // Update maximum
    max = arr[i];
    }
}
 
// Return maximum element
return max;
}
 
// Function to find the prime numbers
// using sieve of eratosthenes algorithm
function sieveOfEratosthenes(max)
{
// Calculate primes using Sieve
prime.fill(true, 0, max + 1)
 
for (let p = 2; p * p < max; p++)
 
    // If current element is prime
    if (prime[p] == true)
 
    // Make all multiples non-prime
    for (let i = p * 2; i < max; i += p)
        prime[i] = false;
}
 
// Function to count divisors of n
function divCount(n)
{
 
// Traversing through
// all prime numbers
let total = 1;
for (let p = 2; p <= n; p++) {
 
    // If it is a prime number
    if (prime[p]) {
 
    // Calculate number of divisors
    // with the formula
    // number of divisors = (p1 + 1) * (p2 + 1)
    // *.....* (pn + 1)
    // n = (a1 ^ p1) * (a2 ^ p2) .... *(an ^ pn)
    // ai: prime divisor of n
    // pi: power in factorization
    let count = 0;
 
    if (n % p == 0) {
 
        while (n % p == 0) {
        n = n / p;
        count++;
        }
        total = total * (count + 1);
    }
    }
}
 
// Return the total number of divisors
return total;
}
 
// Function to count array elements
// having exactly K divisors
function countElements(arr, N, K)
{
 
// Initialize a map to store
// count of divisors of array elements
let map = new Map();
 
// Traverse the array
for (let i = 0; i < N; i++) {
 
    // If element is not already present in
    // the Map, then insert it into the Map
    if (!map.has(arr[i])) {
    // Function call to count the total
    // number of divisors
    map.set(arr[i], divCount(arr[i]));
    }
}
 
// Stores the number of
// elements with divisor K
let count = 0;
 
// Traverse the array
for (let i = 0; i < N; i++) {
 
    // If current element
    // has exactly K divisors
    if (map.get(arr[i]) == K) {
    count++;
    }
}
 
// Return the number of
// elements having K divisors
return count;
}
 
// Driver Code
 
let arr = [ 3, 6, 2, 9, 4 ];
let N = arr.length;
let K = 2;
 
// Find the maximum element
let max = maximumElement(arr, N);
 
// Generate all prime numbers
sieveOfEratosthenes(max);
 
document.write(countElements(arr, N, K));
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(N + maxlog(log(max) + log(max)), donde max es el elemento de array máximo.
Espacio auxiliar: O(max), donde max es el elemento de array máximo.

Publicación traducida automáticamente

Artículo escrito por deepika_sharma 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 *