N個數的乘積的因子個數

一個數的除數是能夠將其整除而沒有任何餘數的數。換句話說，一個數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個數字的乘積的約數數量，包括使用模運算子、質因數分解、嵌套循環等等。對於較大的數字，我們無法有效率地使用模運算子。為了獲得最佳化的結果，我們可以使用質因數分解和嵌套循環的方法。

以上是N個數的乘積的因子個數的詳細內容。更多資訊請關注PHP中文網其他相關文章！