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 divisoresEntrada: 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:
- Encuentre el elemento máximo presente en la array .
- Inicialice una array prime[] .
- Almacene todos los primos presentes en el rango [2, elemento máximo en la array ] en la array primo[] usando Sieve of Eratosthenes .
- Recorre la array y factoriza en factores primos cada elemento de la array usando la fórmula dada:
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