資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給定數字 N 的約數中能被 K 整除的約數個數
查詢給定數字 N 的約數中也能夠被 K（任意常數）整除的約數個數是一個典型的數學問題，需要大量的計算。這裡，K 通常是一個小於或等於 N 的平方根的數字。但是，我們可以構建一個 C++ 程式，透過該程式，計算這些數字將變得更容易。
在本文中，我們將討論 C++ 中的不同方法，使用這些方法我們可以找到上述問題的解決方案。
輸入輸出場景
如果我們考慮以下場景，這裡我們有 N 值為 50，K 值為 5。50 的約數是 1、2、5、10、25、50，其中 5、10、25、50 能被 5 整除。因此，輸出應該為4。
Input: N = 50, K = 5 Output: 4
同樣，如果我們考慮 N 值為 120。
120 的約數是 1、2、3、4、5、6、8、10、12、15、20、24、30、40、60、120。
其中能被 K 即 10 整除的數字是 10、20、30、40、60 和 120。
因此，120 的約數中能被 10 整除的約數個數為6。
Input: N = 120, K = 10 Output: 6
使用 For 迴圈和 && 運算子
這是一種簡單的方法，我們使用for迴圈迭代 1 到 N 之間的值。在for迴圈中，我們使用if語句查詢滿足所需條件的數字的計數。這些條件是：
該數字應該是 N 的約數。
並且應該能被 K 整除。
要檢查數字的可除性，我們使用模運算子。
模運算子 (%) - 此運算子用於獲取除法運算的餘數。如果除法的餘數為零，則表示被除數能被除數整除。例如，(25 % 5) 為 0，因此 25 能被 5 整除。
示例
在下面的示例中，我們嘗試計算 100 的約數中能被 5 整除的約數個數。
#include <iostream>
using namespace std;
int findNumberOfDivisors(int N, int K){
// Variable to store the result
int find = 0, x;
// Iterate from 1 to N
for(x = 1; x <= N; x++){
if (N % x == 0 && x % K == 0){
find++;
}
}
return find;
}
int main(){
// Declaring values of N and K
int N = 100, K = 5;
cout << "Number of divisors of " << N << " which are divisible by " << K << " are " << findNumberOfDivisors(N, K);
return 0;
}
輸出
Number of divisors of 100 which are divisible by 5 are 6
迭代到 N 的平方根
我們還有另一種替代解決方案，在這裡我們將最佳化我們的迴圈，迭代從 1 到 N 的平方根。
在這種方法中，我們將使用約數的一個屬性，該屬性指出約數總是成對出現的，並且其中一個約數小於或等於該數字的平方根。
例如，如果 N = 100，則約數對為：(1, 100)、(2, 50)、(4, 25)、(5, 20)、(10, 10)。
因此，如果迴圈，我們將搜尋小於給定數字的平方根的數字。
然後，我們檢查該數字是否為 N 的約數，並且是否也能被 K 整除。如果兩個條件都滿足，我們將遞增count變數。
為了避免在從 1 到 √(N) 迭代時重複計算同一個約數，我們編寫另一個 if 語句。此外，我們檢查 N/x 是否為 K 的因子（因為 x 是N的約數，並且x能被K整除）。如果兩個條件都滿足，我們需要再次遞增count變數。
此方法減少了所需的迭代次數。因此，它透過降低時間複雜度來提高效能。
注意− cmath是 C++ 標準庫標頭檔案，它使開發人員能夠執行數學函式和運算，如 sin()、cos()、pow()、sqrt() 等。
示例
以下是一個示例：
#include <iostream>
#include <cmath>
using namespace std;
// Function for finding the number
int findNumberOfDivisors(int N, int K){
// variable to store the result
int find = 0, x;
// Iterate from 1 to √(N)
for (x = 1; x <= sqrt(N); x++) {
// Check if x is divisor of N
if (N % x == 0) {
// Check if x is divisible by K
if (x % K == 0) {
find++;
}
if (x != N / x && (N / x) % K == 0) {
find++;
}
}
}
return find;
}
int main(){
// Declaring values of N and K
int N = 100, K = 5;
cout << "Number of divisors of " << N << " which are divisible by " << K << " are " << findNumberOfDivisors(N, K);
return 0;
}
輸出
Number of divisors of 100 which are divisible by 5 are 6
結論
我們已經探索了各種技術，這些技術可用於計算給定數字N的約數中能被K整除的約數個數。我們已經看到了不同的方法，包括在for迴圈中使用模運算子和最佳化的迴圈技術。
模運算子方法是一種易於使用的方法，而最佳化的迴圈技術是一種有效的方法，可以提高效能。現在，問題出現了：哪種方法更好？答案是，這取決於問題的需求和N的大小。
280 次瀏覽
