一个数的除数是能够将其整除而没有任何余数的数。换句话说，一个数n的除数是当乘以任何其他整数时得到n的数。它也可以被称为一个数的因子。

Dividend ÷ Divisor = Quotient.

例如，如果我们用5除以60，我们将得到12，反之亦然，因此，12和60可以被认为是60的除数。

乘以N个数的因子数量

给定任务是找到给定数字的乘积的除数数量。让我们通过一个例子来理解这个问题。

假设我们给出了数字6、6和10。这些数字的乘积是120，120的约数是1、2、3、4、5、6、8、10、12、15、20、24、30、40、60、120。因此，输出应为16。

Input: 6, 2, 10
Output: 16

使用取模运算符

实现这一目标的一种方法是使用 取模（%）运算符找到除数，并通过从 1 迭代到 product 来计数它们。

模运算符 (%) 运算符用于获取除法运算的余数。如果除法的余数为零，则意味着被除数可以被除数整除。例如，(30 % 5) 为 0，因此 30 可以被 5 整除。

计算一个数组中所有数字的乘积的约数个数。

• 使用乘法运算符将数组中的所有数字相乘，并将结果存储在名为product的变量中。

• 使用模运算符，从1到Product，将Product与每个数字相除并获取余数。

• 创建一个变量 count，如果余数为0，则增加 count 变量。

Example

示例

以下程序计算给定数字的乘积的约数数量 −

#include <iostream>
using namespace std;

// Define a function for finding the number
int findNumberOfDivisors(int arr[], int N) {

   // Multiply all the numbers in the array
   int product = 1;
   for (int x = 0; x < N; x++) {
      product *= arr[x];
   }

   // Count the divisors
   int count = 0;
   for (int x = 1; x <= product; x++) {
      if (product % x == 0) {
         count++;
      }
   }

   return count;
}
int main() {

   // Declaration of the numbers and N
   int numbers[] = { 12, 16, 40 };
   int N = sizeof(numbers) / sizeof(numbers[0]);
   int divisors = findNumberOfDivisors(numbers, N);
   std::cout << "Number of divisors: " << divisors;
   return 0;
}

输出

Number of divisors: 40

注意−对于较大的数字，这种方法效率非常低。由于数字较大，乘积也会很大。这将导致大量的迭代，增加时间复杂度。

使用质因数分解

如果N是一个合数，那么

N = x<sup>a</sup>  * y<sup>b</sup>  * z<sup>c</sup>

其中a、b和c是质因数，那么N的约数个数由以下公式给出

(a + 1)(b + 1)(c + 1)

我们将使用上述概念来找到N个数字乘积的约数个数。

算法/步骤

• 将所有N个数字相乘，并将结果存储在一个名为product的变量中。

• 从2迭代一个for循环，直到平方根为止，product。

• 获取乘积的质因数。为此，我们使用模运算符来检查product 是否可以被当前的x值整除。如果可以，x被存储为质因数，而count 被存储为质因数的幂。

• 使用库和push_back()函数将质因数及其指数存储在向量容器primeFactor和power中。

• 如果还有剩余的质因数，请也将它们存储起来。

• 通过从0迭代到质因数的个数，并使用上述公式计算约数。

Example

示例

以下是使用质因数分解方法找到给定数字乘积的因子数量的程序 -

#include <iostream>
#include <vector>
#include <cmath>

// Multiply all the N numbers
int findNumberOfDivisors(int arr[], int N) {
   int product = 1;
   for (int x = 0; x < N; x++) {
      product *= arr[x];
   }

   std::vector<int> primeFactor;
   std::vector<int> power;
    
   // Check if x is divisor of product

   // Store the prime factor and exponent in the vector container
   for (int x = 2; x <= sqrt(product); x++) {
      if (product % x == 0) {
         int count = 0;
         while (product % x == 0) {
            product /= x;
            count++;
         }
         primeFactor.push_back(x);
         power.push_back(count);
      }
   }
    
   // Store the remaining prime factor (if present)  
   if (product > 1) {
      primeFactor.push_back(product);
      power.push_back(1);
   }
    
   // Count the number of divisors
   int divisorsCount = 1;
   for (int x = 0; x < primeFactor.size(); x++) {
      divisorsCount *= (power[x] + 1);
   }

   return divisorsCount;
}

int main() {
   int numbers[] = {12, 16, 40};
   
   // Calculate the number of elements in the array
   int N = sizeof(numbers) / sizeof(numbers[0]);
   int divisors = findNumberOfDivisors(numbers, N);
   std::cout << "Number of divisors: " << divisors << std::endl;
   return 0;
}

输出

Number of divisors: 40

使用嵌套循环

我们还可以通过嵌套循环找到所有N个数字的乘积。在外部循环中，我们需要迭代从1到product的所有数字。在这个数字范围内，我们将找到所有可能的除数。在嵌套循环中，我们将计算每个数字及其倍数的除数数量。

Example

示例

#include <iostream>
#include <vector>

int findNumberOfDivisors(int arr[], int N) {
   std::vector<int> divisorsCount(11000, 0);
    
   // Multiply all the N numbers
   int product = 1;
   for (int x = 0; x < N; x++) {
      product *= arr[x];
    }
    
   // Count of divisors
   for (int x = 1; x <= product; x++) {
      for (int y = x; y <= product; y += x) {
         divisorsCount[y]++;
      }
   }

   return divisorsCount[product];
}

int main() {
   int numbers[] = {12, 16, 40};
   int N = sizeof(numbers) / sizeof(numbers[0]);
   int divisors = findNumberOfDivisors(numbers, N);
   std::cout << "Number of divisors: " << divisors << std::endl;
   return 0;
}

输出

Number of divisors: 40

结论

我们已经讨论了不同的方法来找到N个数字的乘积的约数数量，包括使用模运算符、质因数分解、嵌套循环等等。对于较大的数字，我们无法高效地使用模运算符。为了获得优化的结果，我们可以使用质因数分解和嵌套循环的方法。