数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
