資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究N個數字乘積的約數個數
數的約數是指能整除該數且沒有餘數的數。換句話說，數n的約數是指與任何其他整數相乘後結果為n的數。它也可以稱為數的因數。
Dividend ÷ Divisor = Quotient.
例如，如果我們將60除以5，我們將得到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迭代到乘積來計算它們。
取模運算子（%）運算子用於獲取除法運算的餘數。如果除法的餘數為零，則表示被除數可以被除數整除。例如，（30 % 5）為0，因此30可以被5整除。
計算數字陣列乘積的約數個數。
使用乘法運算子將陣列的所有數字相乘，並將值儲存在名為乘積的變數中。
使用取模運算子，從1到乘積，用每個數字除以乘積並獲取餘數。
建立一個變數計數，如果餘數為0，則遞增計數變數。
示例
以下程式計算給定數字乘積的約數個數：
#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 = xa * yb * zc
其中a、b和c是質因數，則N的約數個數由下式給出
(a + 1)(b + 1)(c + 1)
我們將使用上述概念來找到N個數字乘積的約數個數。
演算法/步驟
將所有N個數字相乘並將其儲存在名為乘積的變數中。
迭代一個for迴圈，從2到乘積的平方根。
獲取乘積的質因數。為此，我們使用取模運算子來檢查乘積是否可以被x的當前值整除。如果是，則x被儲存為質因數，而計數被儲存為質因數的冪。
使用<vector>庫和push_back()函式，將質因數及其指數儲存在向量容器-primeFactor和power中。
如果有任何剩餘的質因數，也將其儲存。
透過從0迭代到質因數的數量並使用上述公式來計算約數。
示例
以下是使用質因數分解方法查詢給定數字乘積的約數個數的程式：
#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到乘積的所有數字。在這個數字範圍內，我們將找到所有可能的約數。在巢狀迴圈中，我們將計算每個數字及其倍數的約數個數。
示例
#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個數字乘積的約數個數的不同方法，包括使用取模運算子、質因數分解、巢狀迴圈等。我們不能有效地對較大的數字使用取模運算子。為了獲得最佳化的結果，我們可以使用質因數分解和巢狀迴圈方法。
274 次檢視
