資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中計算 L 和 R 之間與 P 互質的數字個數
在計算機程式設計領域，查詢給定範圍內與特定數字互質的數字個數是一個常見任務。互質數，也稱為互素數，是指除了 1 之外沒有其他公因數的數字。在本篇文章中，我們將藉助 C++ 語言深入探討如何在給定兩個整數 L 和 R 的情況下，找到與特定數字 P 互質的數字個數。
語法
我們將首先概述將在後續程式碼示例中使用的該方法的語法 -
int countCoprimes(int L, int R, int P);
演算法
我們將使用以下演算法來計算互質數的個數 -
將一個變數 count 初始化為 0，它將儲存互質數的個數。
迭代每個數字 num，從 L 到 R。
對於每個 num，檢查它是否與 P 互質。
如果 num 和 P 互質，則將 count 加 1。
返回 count 的最終值。
方法 1：樸素方法
我們將討論的第一種方法是樸素方法。為了使用歐幾里得演算法驗證與 P 的互質性，此方法需要透過迭代檢查指定範圍內的每個數字。
示例
#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
解釋
countCoprimes 函式接受三個引數：L（起始範圍值）、R（結束範圍值）和 P（P 的值）。
在 countCoprimes 函式內部，我們將一個變數 count 初始化為 0，它將儲存互質數的個數。
for 迴圈迭代每個數字 num，從 L 到 R。
在迴圈內部，我們將變數 a 和 b 分別初始化為 num 和 P。
我們在 while 迴圈中使用歐幾里得演算法透過重複交換和執行模運算來找到 a 和 b 的最大公約數 (GCD)。
如果 GCD（儲存在 a 中）等於 1，則表示 num 和 P 互質。在這種情況下，我們將 count 變數加 1。
在我們仔細迭代完所有數字後，透過返回它來完成我們的 count 值。
main 函式為 L、R 和 P 變數分配合適的值。
然後，我們使用提供的 value 呼叫 countCoprimes 函式並將結果儲存在 result 變數中。
最後，我們顯示 result，它是 L 和 R 之間與 P 互質的數字個數。
方法 2：質因數分解
此策略涉及利用 P 的質因數分解來精確計算落在 L 和 R 之間的互質整數的個數。
示例
#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
解釋
countCoprimes 函式接受三個引數：L（起始範圍值）、R（結束範圍值）和 P（P 的值）。
我們建立一個無序集合 factors 來儲存 P 的質因數。我們將一個臨時變數 tempP 初始化為 P。
我們從 2 迭代到 tempP 的平方根。如果 tempP 可以被 i 整除，我們將 i 新增到集合 factors 中，並將 tempP 除以 i，直到它不再可以被 i 整除。
如果上述迴圈後 tempP 大於 1，則表示它本身是一個質數，應將其新增到 factors 中。
我們將一個變數 count 初始化為 0，它將儲存互質數的個數。
我們迭代每個數字 num，從 L 到 R，並檢查它是否可以被集合 factors 中的任何因數整除。如果是，則將其標記為非互質。
在完成所有數字的迭代後，將結果 count 作為最終值返回。至於 main 函式，它使用指定的值初始化 L、R 和 P。
然後，我們使用提供的 value 呼叫 countCoprimes 函式並將結果儲存在 result 變數中。
最後，我們顯示 result，它是 L 和 R 之間與 P 互質的數字個數。
結論
在指定的 L-R 範圍內計算互質數並尊重某個特定值 P 對程式設計師來說是一個有趣的挑戰——但在細粒度的程式碼級別上解決此問題的最佳方法是什麼？作為本文的一部分，我們深入探討了兩種 C++ 用例，它們在解決此類問題時提供了真正的效率。首先是在該目標區間內迭代所有值並使用歐幾里得演算法檢查這些數字是否匹配為互質數；或者可以使用尤拉 phi 函式方法，該方法採用最佳化策略。充分利用任一方法可能高度依賴於上下文因素，例如您選擇的數字和指定的區間，但在兩種可能的方法之間做出明智的選擇確實可以加快程式的整體執行速度。對於希望將其技術技巧和創造性解決問題的能力新增到其技能庫中的編碼人員來說，透過這些方法掌握使用 C++ 進行互質計數可能是他們需要的恰到好處的方法。
248 次瀏覽
