极客笔记C++ 计算在给定范围L和R之间与P互质的数字的数量
在计算机编程领域，计算在给定范围内与特定数字互质的数字的数量是一个常见的任务。互质数，也称为相对质数，是除了1以外没有其他公共因数的数。在本文中，我们将探讨在C++语言中如何找到在给定整数L和R之间与特定数字P互质的数的数量。
语法
我们将以以下语法概述我们在下面的代码示例中将使用的方法：
int countCoprimes(int L, int R, int P);
步骤
我们将使用以下算法来计算互质数的个数：
- 初始化一个变量count为0，它将存储互质数的个数。
-
从L到R遍历每个数字num。
-
对于每个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循环遍历从L到R的每个数字num。
在循环内部，我们分别将变量a和b初始化为num和P。
我们在while循环中使用欧几里得算法来找到a和b的最大公约数（GCD），通过重复交换和执行取模操作。
如果GCD（存储在a中）等于1，意味着num和P是互质的。在这种情况下，我们递增计数变量。
一旦我们仔细地遍历了所有数字，我们通过返回计数值来完成计数。
main函数仔细地为L、R和P变量分配适当的值。
然后，我们使用提供的值调用countCoprimes函数，并将结果存储在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直到tempP不再能被i整除。
如果上述循环结束后tempP大于1，则说明tempP本身是一个质数，应该将其添加到factors中。
我们初始化一个变量count为0，用于存储互质数的数量。
我们从L到R迭代每个数num，并检查它是否能被集合factors中的任何因数整除。如果可以，则标记为非互质数。
完成所有数字的迭代后，将得到的count作为最终值返回。至于主函数，它使用指定的值初始化L、R和P。
然后，我们使用提供的值调用countCoprimes函数，并将结果存储在result变量中。
最后，我们显示结果，即L和R之间与P互质的数字的计数。
结论
在指定范围L-R内计算互质数字，并遵守特定值P，对程序员来说是一个不错的挑战-但在代码级别上应该使用什么样的最佳方法呢？作为本文的一部分，我们深入研究了两个C++使用情况，这些情况在处理此类问题时提供了真正的效率。首先，有在目标区间内对所有值进行迭代，并使用欧几里得算法检查这些数字是否匹配作为互质数的方法；另外，还有使用优化策略的欧拉phi函数方法。选择哪种方法来最大化性能可能高度取决于上下文因素，如所选择的数字和指定的区间，但在这两种方法之间做出明智的选择，确实可以加快整体程序执行速度。对于那些希望为他们的技术精湛和创造性解决问题的技术人员，通过这些方法使用C++来掌握互质计数可能正是他们所需要的。