在電腦程式設計領域，找到給定範圍內與特定數字互質的數字數量可能是常見的任務。互質數，也稱為相對質數，是指除了1以外沒有其他公因數的數字。在本文中，我們將透過使用C 語言來探討在給定整數L和R之間找到與特定數字P互質的數字數。
文法
我們將首先概述我們在接下來的程式碼範例中將使用的方法的語法 -
int countCoprimes(int L, int R, int P);
登入後複製
演算法
我們將使用的演算法來計算互質數的數量如下所示−
方法1：樸素方法
我們將要討論的第一種方法是樸素方法。為了使用歐幾裡得演算法來驗證與P的互質性，這種方法需要透過迭代來檢查指定範圍內的每個數字。
Example
的中文翻譯為：
範例
#include <iostream>
int countCoprimes(int L, int R, int P) {
int count = 0;
for (int num = L; num <= R; num++) {
int a = num;
int b = P;
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
if (a == 1)
count++;
}
return count;
}
int main() {
int L = 1; // Set the starting range value
int R = 100; // Set the ending range value
int P = 7; // Set the value of P
int result = countCoprimes(L, R, P);
std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
return 0;
}
登入後複製
輸出
Count of numbers between 1 and 100 coprime with 7: 86
登入後複製
登入後複製
Explanation
的中文翻譯為：
解釋
countCoprimes函數接受三個參數：L（起始範圍值），R（結束範圍值）和P（P的值）。
在countCoprimes函數內部，我們初始化一個變數count為0，它將儲存互質數的數數。
for迴圈迭代從L到R的每個數字num。
在迴圈中，我們分別將變數a和b初始化為num和P。
我們在while循環中使用歐幾里德演算法，透過重複交換和執行模運算來找到a和b的最大公約數（GCD）。
如果GCD（儲存在a中）等於1，這表示num和P是互質的。在這種情況下，我們增加計數變數。
我們透過仔細迭代所有數字來最終確定我們的計數值，並在完成後將其返回。
主要功能周到地為L、R和P變數分配合適的值。
然後我們使用提供的值來呼叫countCoprimes函數，並將結果儲存在result變數中。
最後，我們顯示結果，即在L和R之間與P互質的數字的計數。
方法二：質因數分解
這種策略涉及利用 P 的質因數分解以精確計算落在 L 和 R 之間的互質整數的數量。
Example
的中文翻譯為：
範例
#include <iostream>
#include <unordered_set>
int countCoprimes(int L, int R, int P) {
std::unordered_set<int> factors;
int tempP = P;
for (int i = 2; i * i <= tempP; i++) {
while (tempP % i == 0) {
factors.insert(i);
tempP /= i;
}
}
if (tempP > 1)
factors.insert(tempP);
int count = 0;
for (int num = L; num <= R; num++) {
bool isCoprime = true;
for (int factor : factors) {
if (num % factor == 0) {
isCoprime = false;
break;
}
}
if (isCoprime)
count++;
}
return count;
}
int main() {
int L = 1; // Set the starting range value
int R = 100; // Set the ending range value
int P = 7; // Set the value of P
int result = countCoprimes(L, R, P);
std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
return 0;
}
登入後複製
輸出
Count of numbers between 1 and 100 coprime with 7: 86
登入後複製
登入後複製
Explanation
的中文翻譯為：
解釋
countCoprimes函數接受三個參數：L（起始範圍值），R（結束範圍值）和P（P的值）。
我們建立一個無序因子集合來儲存P的質因子。我們將一個暫存變數tempP初始化為P。
我們從2迭代到tempP的平方根。如果tempP可以被i整除，我們將i加到因子集合中，並將tempP除以i，直到tempP不再能被i整除。
如果上述循環後tempP大於1，表示它本身是質數，應該加到因子中。
我們將變數count初始化為0，它將儲存互質數的計數。
我們迭代遍歷從L到R的每個數字num，並檢查它是否可以被集合factors中的任何一個因子整除。如果可以，我們將其標記為非互質。
完成所有數字的迭代後，將返回結果計數作為最終值。至於主函數，它使用指定的值初始化L、R和P。
然後我們使用提供的值來呼叫countCoprimes函數，並將結果儲存在result變數中。
最後，我們顯示結果，即在L和R之間與P互質的數字的計數。
結論
在指定的範圍L-R內計算互質數，並且滿足特定值P，對於程式設計師來說是一個不錯的挑戰 - 但是在程式碼層面上，最佳的方法是什麼？作為本文的一部分，我們深入研究了兩個C 使用案例，這些案例在解決此類問題時提供了真正的效率。首先，透過迭代在目標區間內的所有值，並使用歐幾里德演算法檢查這些數字是否符合為互質數；另外，還有使用歐拉函數方法，該方法使用了最佳化策略。無論是哪種方法，能否充分發揮其優勢很大程度上取決於上下文因素，例如您選擇的數字和指定的區間，但在兩種可能的方法之間做出明智的選擇，確實可以加快整體程式的執行速度。對於希望在他們的技術技巧和創造性問題解決能力中增加技術精湛的編碼人員來說，透過這些方法使用C 來掌握互質數計數可能正是他們所需要的。
以上是在C++中，將以下內容翻譯為中文：計算在L和R之間與P互質的數字數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
