Dada una array arr[] de enteros, la tarea es contar el número de divisores del producto de todos los elementos de la array dada.
Ejemplos:
Entrada: arr[] = {3, 5, 7}
Salida: 8
3 * 5 * 7 = 105.
Los factores de 105 son 1, 3, 5, 7, 15, 21, 35 y 105.
Entrada: arr[] = {5, 5}
Resultado: 3
5 * 5 = 25.
Los factores de 25 son 1, 5 y 25.
Una solución simple es multiplicar todos los N enteros y contar el número de divisores del producto. Sin embargo, si el producto supera 10 7 , entonces no podemos usar este método porque los números mayores que 10^7 no se pueden factorizar en primos eficientemente usando el método de criba.
Una solución eficiente no implica el cálculo del producto de todos los números. Ya sabemos que cuando multiplicamos 2 números, se suman potencias. Por ejemplo,
A = 2 7 , B = 2 3
A * B = 2 10
Por lo tanto, necesitamos mantener la cuenta de cada potencia en el producto de números, lo que se puede hacer sumando cuentas de potencias de cada elemento.
Por lo tanto, para calcular el número de divisores, el enfoque principal está en el conteo de números primos encontrados. Por lo tanto, haremos hincapié solo en los números primos que se encuentran en el producto sin preocuparnos por el producto en sí. Mientras recorremos la array, mantenemos la cuenta de cada número primo encontrado.
Número de divisores = (p 1 + 1) * (p 2 + 1) * (p 3 + 1) * … * (p n + 1)
donde p 1 , p 2 , p 3 , …, p n son los números primos encontradas en la descomposición en factores primos de todos los elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define MAX 10000002
using namespace std;
int prime[MAX];
// Array to store count of primes
int prime_count[MAX];
// Function to store smallest prime factor
// of every number till MAX
void sieve()
{
memset(prime, 0, sizeof(prime));
prime[0] = prime[1] = 1;
for (int i = 2; i * i < MAX; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < MAX; j += i) {
if (prime[j] == 0)
prime[j] = i;
}
}
}
for (int i = 2; i < MAX; i++) {
// If the number is prime then it's
// smallest prime factor is the number
// itself
if (prime[i] == 0)
prime[i] = i;
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
long long numberOfDivisorsOfProduct(const int* arr,
int n)
{
memset(prime_count, 0, sizeof(prime_count));
for (int i = 0; i < n; i++) {
int temp = arr[i];
while (temp != 1) {
// Increase the count of prime
// encountered
prime_count[prime[temp]]++;
temp = temp / prime[temp];
}
}
long long ans = 1;
// Multiplying the count of primes
// encountered
for (int i = 2; i < MAX; i++) {
ans = ans * (prime_count[i] + 1);
}
return ans;
}
// Driver code
int main()
{
sieve();
int arr[] = { 2, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << numberOfDivisorsOfProduct(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
// Java implementation of the approach
class GFG {
final static int MAX = 10000002;
static int prime[] = new int[MAX];
// Array to store count of primes
static int prime_count[] = new int[MAX];
// Function to store smallest prime factor
// of every number till MAX
static void sieve() {
Arrays.fill(prime, 0, MAX, 0);
prime[0] = prime[1] = 1;
for (int i = 2; i * i < MAX; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < MAX; j += i) {
if (prime[j] == 0) {
prime[j] = i;
}
}
}
}
for (int i = 2; i < MAX; i++) {
// If the number is prime then it's
// smallest prime factor is the number
// itself
if (prime[i] == 0) {
prime[i] = i;
}
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
static long numberOfDivisorsOfProduct(int[] arr,
int n) {
Arrays.fill(prime_count, 0, MAX, 0);
for (int i = 0; i < n; i++) {
int temp = arr[i];
while (temp != 1) {
// Increase the count of prime
// encountered
prime_count[prime[temp]]++;
temp = temp / prime[temp];
}
}
long ans = 1;
// Multiplying the count of primes
// encountered
for (int i = 2; i < MAX; i++) {
ans = ans * (prime_count[i] + 1);
}
return ans;
}
// Driver code
public static void main(String[] args) {
sieve();
int arr[] = {2, 4, 6};
int n = arr.length;
System.out.println(numberOfDivisorsOfProduct(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach MAX = 10000002 prime = [0] * (MAX) MAX_sqrt = int(MAX ** (0.5)) # Array to store count of primes prime_count = [0] * (MAX) # Function to store smallest prime # factor in prime[] def sieve(): prime[0], prime[1] = 1, 1 for i in range(2, MAX_sqrt): if prime[i] == 0: for j in range(i * 2, MAX, i): if prime[j] == 0: prime[j] = i for i in range(2, MAX): # If the number is prime then it's # the smallest prime factor is the # number itself if prime[i] == 0: prime[i] = i # Function to return the count of the divisors for # the product of all the numbers from the array def numberOfDivisorsOfProduct(arr, n): for i in range(0, n): temp = arr[i] while temp != 1: # Increase the count of prime # encountered prime_count[prime[temp]] += 1 temp = temp // prime[temp] ans = 1 # Multiplying the count of primes # encountered for i in range(2, len(prime_count)): ans = ans * (prime_count[i] + 1) return ans # Driver code if __name__ == "__main__": sieve() arr = [2, 4, 6] n = len(arr) print(numberOfDivisorsOfProduct(arr, n)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
public class GFG {
static int MAX = 1000000;
static int []prime = new int[MAX];
// Array to store count of primes
static int []prime_count = new int[MAX];
// Function to store smallest prime factor
// of every number till MAX
static void sieve() {
for(int i =0;i<MAX;i++)
prime[i]=0;
prime[0] = prime[1] = 1;
for (int i = 2; i * i < MAX; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < MAX; j += i) {
if (prime[j] == 0) {
prime[j] = i;
}
}
}
}
for (int i = 2; i < MAX; i++) {
// If the number is prime then it's
// smallest prime factor is the number
// itself
if (prime[i] == 0) {
prime[i] = i;
}
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
static long numberOfDivisorsOfProduct(int[] arr,
int n) {
for(int i =0;i<MAX;i++)
prime_count[i]=0;
for (int i = 0; i < n; i++) {
int temp = arr[i];
while (temp != 1) {
// Increase the count of prime
// encountered
prime_count[prime[temp]]++;
temp = temp / prime[temp];
}
}
long ans = 1;
// Multiplying the count of primes
// encountered
for (int i = 2; i < MAX; i++) {
ans = ans * (prime_count[i] + 1);
}
return ans;
}
// Driver code
public static void Main() {
sieve();
int []arr = {2, 4, 6};
int n = arr.Length;
Console.Write(numberOfDivisorsOfProduct(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
let MAX = 10000002
let prime = new Array(MAX);
// Array to store count of primes
let prime_count = new Array(MAX);
// Function to store smallest prime factor
// of every number till MAX
function sieve() {
prime.fill(0)
prime[0] = prime[1] = 1;
for (let i = 2; i * i < MAX; i++) {
if (prime[i] == 0) {
for (let j = i * 2; j < MAX; j += i) {
if (prime[j] == 0)
prime[j] = i;
}
}
}
for (let i = 2; i < MAX; i++) {
// If the number is prime then it's
// smallest prime factor is the number
// itself
if (prime[i] == 0)
prime[i] = i;
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
function numberOfDivisorsOfProduct(arr, n) {
prime_count.fill(0)
for (let i = 0; i < n; i++) {
let temp = arr[i];
while (temp != 1) {
// Increase the count of prime
// encountered
prime_count[prime[temp]]++;
temp = temp / prime[temp];
}
}
let ans = 1;
// Multiplying the count of primes
// encountered
for (let i = 2; i < MAX; i++) {
ans = ans * (prime_count[i] + 1);
}
return ans;
}
// Driver code
sieve();
let arr = [2, 4, 6];
let n = arr.length;
document.write(numberOfDivisorsOfProduct(arr, n));
// This code is contributed by gfgking
</script>
Producción:
10
En un enfoque eficiente de la memoria , la array se puede reemplazar por un mapa desordenado para almacenar el recuento de solo los números primos que se han encontrado.
A continuación se muestra la implementación del enfoque de memoria eficiente:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define MAX 10000002
using namespace std;
int prime[MAX];
// Map to store count of primes
unordered_map<int, int> prime_count;
// Function to store smallest prime factor
// in prime[]
void sieve()
{
memset(prime, 0, sizeof(prime));
prime[0] = prime[1] = 1;
for (int i = 2; i * i < MAX; i++) {
if (prime[i] == 0) {
for (int j = i * 2; j < MAX; j += i) {
if (prime[j] == 0)
prime[j] = i;
}
}
}
for (int i = 2; i < MAX; i++) {
// If the number is prime then
// it's the smallest prime factor
// is the number itself
if (prime[i] == 0)
prime[i] = i;
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
long long numberOfDivisorsOfProduct(const int* arr,
int n)
{
for (int i = 0; i < n; i++) {
int temp = arr[i];
while (temp != 1) {
// Increase the count of prime
// encountered
prime_count[prime[temp]]++;
temp = temp / prime[temp];
}
}
long long ans = 1;
// Multiplying the count of primes
// encountered
unordered_map<int, int>::iterator it;
for (it = prime_count.begin();
it != prime_count.end(); it++) {
ans = ans * (it->second + 1);
}
return ans;
}
// Driver code
int main()
{
sieve();
int arr[] = { 3, 5, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << numberOfDivisorsOfProduct(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 10000002;
static int []prime = new int[MAX];
// Map to store count of primes
static Map<Integer, Integer> prime_count = new HashMap<>();
// Function to store smallest prime factor
// in prime[]
static void sieve()
{
prime[0] = 1;
prime[1] = 1;
for (int i = 2; i * i < MAX; i++)
{
if (prime[i] == 0)
{
for (int j = i * 2; j < MAX; j += i)
{
if (prime[j] == 0)
prime[j] = i;
}
}
}
for (int i = 2; i < MAX; i++)
{
// If the number is prime then
// it's the smallest prime factor
// is the number itself
if (prime[i] == 0)
prime[i] = i;
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
static long numberOfDivisorsOfProduct(int arr[],
int n)
{
for (int i = 0; i < n; i++)
{
int temp = arr[i];
while (temp != 1)
{
// Increase the count of prime
// encountered
if(!prime_count.containsKey(prime[temp]))
{
prime_count.put(prime[temp], 0);
}
prime_count.put(prime[temp], prime_count.get(prime[temp]) + 1);
temp = temp / prime[temp];
}
}
long ans = 1;
// Multiplying the count of primes
// encountered
for(Map.Entry<Integer,Integer> it : prime_count.entrySet())
{
ans = ans * (it.getValue() + 1);
}
return ans;
}
// Driver code
public static void main(String []args)
{
sieve();
int arr[] = new int[] { 3, 5, 7 };
int n = arr.length;
System.out.print(numberOfDivisorsOfProduct(arr, n));
}
}
// This code is contributed by rutvik_56.
Python3
# Python3 implementation of the approach from collections import defaultdict MAX = 10000002 prime = [0] * (MAX) MAX_sqrt = int(MAX ** (0.5)) # Map to store count of primes prime_count = defaultdict(lambda:0) # Function to store smallest prime # factor in prime[] def sieve(): prime[0], prime[1] = 1, 1 for i in range(2, MAX_sqrt): if prime[i] == 0: for j in range(i * 2, MAX, i): if prime[j] == 0: prime[j] = i for i in range(2, MAX): # If the number is prime then # it's the smallest prime factor # is the number itself if prime[i] == 0: prime[i] = i # Function to return the count of the divisors for # the product of all the numbers from the array def numberOfDivisorsOfProduct(arr, n): for i in range(0, n): temp = arr[i] while temp != 1: # Increase the count of prime # encountered prime_count[prime[temp]] += 1 temp = temp // prime[temp] ans = 1 # Multiplying the count of primes # encountered for key in prime_count: ans = ans * (prime_count[key] + 1) return ans # Driver code if __name__ == "__main__": sieve() arr = [3, 5, 7] n = len(arr) print(numberOfDivisorsOfProduct(arr, n)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
static int MAX = 10000002;
static int []prime = new int[MAX];
// Map to store count of primes
static Dictionary<int,int> prime_count = new Dictionary<int,int>();
// Function to store smallest prime factor
// in prime[]
static void sieve()
{
prime[0] = 1;
prime[1] = 1;
for (int i = 2; i * i < MAX; i++)
{
if (prime[i] == 0)
{
for (int j = i * 2; j < MAX; j += i)
{
if (prime[j] == 0)
prime[j] = i;
}
}
}
for (int i = 2; i < MAX; i++)
{
// If the number is prime then
// it's the smallest prime factor
// is the number itself
if (prime[i] == 0)
prime[i] = i;
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
static long numberOfDivisorsOfProduct(int []arr,
int n)
{
for (int i = 0; i < n; i++)
{
int temp = arr[i];
while (temp != 1)
{
// Increase the count of prime
// encountered
if(!prime_count.ContainsKey(prime[temp]))
{
prime_count[prime[temp]] = 0;
}
prime_count[prime[temp]] += 1;
temp = temp / prime[temp];
}
}
long ans = 1;
// Multiplying the count of primes
// encountered
foreach(KeyValuePair<int,int> it in prime_count)
{
ans = ans * (it.Value + 1);
}
return ans;
}
// Driver code
public static void Main(string []args)
{
sieve();
int []arr = new int[] { 3, 5, 7 };
int n = arr.Length;
Console.Write(numberOfDivisorsOfProduct(arr, n));
}
}
// This code is contributed by pratham76.
Javascript
<script>
// Javascript implementation of the approach
let MAX = 10000002;
let prime = new Array(MAX);
for(let i=0;i<MAX;i++)
prime[i]=0;
// Map to store count of primes
let prime_count = new Map();
// Function to store smallest prime factor
// in prime[]
function sieve()
{
prime[0] = 1;
prime[1] = 1;
for (let i = 2; i * i < MAX; i++)
{
if (prime[i] == 0)
{
for (let j = i * 2; j < MAX; j += i)
{
if (prime[j] == 0)
prime[j] = i;
}
}
}
for (let i = 2; i < MAX; i++)
{
// If the number is prime then
// it's the smallest prime factor
// is the number itself
if (prime[i] == 0)
prime[i] = i;
}
}
// Function to return the count of the divisors for
// the product of all the numbers from the array
function numberOfDivisorsOfProduct(arr,n)
{
for (let i = 0; i < n; i++)
{
let temp = arr[i];
while (temp != 1)
{
// Increase the count of prime
// encountered
if(!prime_count.has(prime[temp]))
{
prime_count.set(prime[temp], 0);
}
prime_count.set(prime[temp], prime_count.get(prime[temp]) + 1);
temp = Math.floor(temp / prime[temp]);
}
}
let ans = 1;
// Multiplying the count of primes
// encountered
for(let it of prime_count.values())
{
ans = ans * (it + 1);
}
return ans;
}
// Driver code
sieve();
let arr = [ 3, 5, 7 ];
let n = arr.length;
document.write(numberOfDivisorsOfProduct(arr, n));
// This code is contributed by unknown2108
</script>
Producción:
8
Publicación traducida automáticamente
Artículo escrito por rohan23chhabra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA