如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。 例如 都是既约分数。 请问，有多少个既约分数，分子和分母都是1到n 之间的整数（包括1 和 n）？ 输入 一个正整数n 输出 输出既约分数的个数 样例输入 复制 5 样例输出 复制 19 回答篇幅：越详细越好

问题分析 要计算分子和分母都是 1 到 `n` 之间的整数（包括 1 和 `n`）的既约分数的个数。既约分数是指分子和分母的最大公约数是 1 的分数。可以通过双重循环遍历分子和分母的所有可能组合，对于每一对分子分母，判断它们的最大公约数是否为 1，如果是则该分数为既约分数，计数器加 1。 代码实现（Python） ```python # 定义一个函数用于计算两个数的最大公约数 def gcd(a, b): # 当 b 不为 0 时，进行辗转相除 while b: # 将 a 赋值为 b，b 赋值为 a 除以 b 的余数 a, b = b, a % b # 最终 a 就是最大公约数 return a # 获取用户输入的正整数 n n = int(input()) # 初始化既约分数的计数器为 0 count = 0 # 外层循环遍历分子，从 1 到 n for numerator in range(1, n + 1): # 内层循环遍历分母，从 1 到 n for denominator in range(1, n + 1): # 判断分子和分母的最大公约数是否为 1 if gcd(numerator, denominator) == 1: # 如果是既约分数，计数器加 1 count = count + 1 # 输出既约分数的个数 print(count) ``` 代码解释 1. 最大公约数函数 `gcd`：该函数使用辗转相除法计算两个数的最大公约数。辗转相除法的原理是：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。 2. 输入处理：使用 `input()` 函数获取用户输入的正整数 `n`，并使用 `int()` 函数将其转换为整数类型。 3. 双重循环：外层循环遍历分子，从 1 到 `n`；内层循环遍历分母，从 1 到 `n`。对于每一对分子分母，调用 `gcd` 函数判断它们的最大公约数是否为 1。 4. 计数器：使用 `count` 变量记录既约分数的个数，当分子和分母的最大公约数为 1 时，`count` 加 1。 5. 输出结果：最后使用 `print` 函数输出既约分数的个数。 复杂度分析 - 时间复杂度：$O(n^2 \log n)$，其中 $n$ 是输入的正整数。双重循环遍历分子和分母的所有可能组合，时间复杂度为 $O(n^2)$；每次调用 `gcd` 函数的时间复杂度为 $O(\log n)$。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 样例测试 对于样例输入 `5`，程序会计算分子和分母都是 1 到 5 之间的既约分数的个数，并输出结果 `19`。 [2026-01-24 13:07:42 | AI问答 | 708点数解答]