CPP 中 L 和 R 之间与 P 互质的数的计数
在计算机编程领域，查找给定范围内与特定数字互质的数的计数可能是一项常见任务。互质数，也称为相对质数，是那些除了 1 之外没有共同因子的数。在本文中，我们将借助 C++ 语言深入研究在引用特定数字 P 时查找两个给定整数 L 和 R 之间的互质数计数。
语法
我们将首先概述我们将在后续代码示例中使用的方法的语法 -
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; // 设置起始范围值
int R = 100; // 设置结束范围值
int P = 7; // 设置 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 互质。在这种情况下，我们增加计数变量。
在仔细迭代所有数字后，我们通过返回计数值来确定最终计数值。
主函数会仔细为 L、R 和 P 变量分配合适的值。
然后，我们使用提供的值调用 countCoprimes 函数，并将结果存储在结果变量中。
最后，我们显示结果，即 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; // 设置起始范围值
int R = 100; // 设置结束范围值
int P = 7; // 设置 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 的值)。
我们创建一个无序的因子集来存储 P 的素因子。我们将临时变量 tempP 初始化为 P。
我们从 2 迭代到 tempP 的平方根。如果 temp P 能被 i 整除，我们将 i 添加到因子集合中，并将 tempP 除以 i，直到它不能再被 i 整除。
如果 tempP 在上述循环之后大于 1，则意味着它本身就是素数，应该添加到因子中。
我们将变量 count 初始化为 0，它将存储互质数的数量。
我们从 L 开始到 R 遍历每个数字 num，并检查它是否能被因子集合中的任何因子整除。如果是，我们将其标记为非互质。
完成所有数字的迭代后，结果计数将作为最终值返回。至于主函数，它使用指定的值初始化 L、R 和 P。
然后我们使用提供的值调用 countCoprimes 函数并将结果存储在结果变量中。
最后，我们显示结果，即 L 和 R 之间与 P 互质的数字的数量。
结论
计算指定范围 L-R 内的互质数并尊重某个特定值 P 对程序员来说是一项艰巨的挑战 - 但在细粒度代码级别上解决此问题的最佳方法是什么?作为本文的一部分，我们深入研究了两个 C++ 用例，它们在解决此类问题时提供了真正的效率。首先，使用欧几里得算法迭代该目标间隔内的所有值并检查这些数字是否匹配为互质数；或者，使用欧拉的 phi 函数方法，它采用优化策略。能否充分利用这两种方法在很大程度上取决于上下文因素，例如您选择的数字和指定的间隔，但在两种可能的方法之间做出明智的选择确实可以加快您的程序整体执行速度。对于希望在其技能库中添加技术技巧和创造性解决问题技能的程序员来说，通过这些方法掌握 C++ 互质计数可能正是他们所需要的。
