Количество делителей произведения N чисел

Опубликовано: 5 Января, 2022

Учитывая массив целых чисел arr [] , задача состоит в том, чтобы подсчитать количество делителей произведения всех элементов данного массива.
Примеры:

Input: arr[] = {3, 5, 7} 
Output: 8 
3 * 5 * 7 = 105. 
Factors of 105 are 1, 3, 5, 7, 15, 21, 35 and 105.
Input: arr[] = {5, 5} 
Output: 3 
5 * 5 = 25. 
Factors of 25 are 1, 5 and 25. 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простое решение - умножить все N целых чисел и посчитать количество делителей произведения. Однако, если произведение превышает 10 7, мы не можем использовать этот подход, потому что числа больше 10 ^ 7 не могут быть эффективно разложены на простые множители с использованием подхода сита.
Эффективное решение не предполагает вычисления произведения всех чисел. Мы уже знаем, что когда мы умножаем 2 числа, степени складываются. Например,

A = 27, B = 23 
A * B = 210 
Therefore, we need to maintain the count of every power in the product of numbers which can be done by adding counts of powers from every element. 
 

Следовательно, при вычислении числа делителей основное внимание уделяется подсчету встречающихся простых чисел. Поэтому мы будем делать упор только на простых элементах, встречающихся в продукте, не беспокоясь о самом продукте. Обходя массив, мы ведем подсчет всех встреченных простых чисел.

Number of divisors = (p1 + 1) * (p2 + 1) * (p3 + 1) * … * (pn + 1) 
where p1, p2, p3, …, pn are the primes encountered in the prime factorization of all the elements. 
 

Ниже представлена реализация описанного выше подхода:

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 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>
Выход:
 10

В подходе с эффективным использованием памяти массив может быть заменен неупорядоченной картой для хранения количества только тех простых чисел, которые были встречены.
Ниже представлена реализация подхода с эффективным использованием памяти:

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 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<
Technical Scripter Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023