给定整数 ，求 且 为素数的数对 有多少对。 即求 的最大公约数。 输入 输入一个整数 ， 输出 输出一个整数，表示满足条件的数对数量。 样例输入 复制 4 样例输出 复制 8

以下是对该问题的分析与Python代码实现： 问题分析 本题需要找出满足条件的数对 `(x, y)` 的数量，条件为 `1 <= x, y <= n` 且 `gcd(x, y)` 为素数。解题的步骤如下： 1. 生成小于等于 `n` 的所有素数。 2. 对于每个素数 `p`，遍历 `x` 和 `y` 的所有可能取值，计算 `gcd(x, y)`，若 `gcd(x, y)` 等于该素数，则该数对满足条件。 3. 统计满足条件的数对数量。 Python代码实现 ```python import math # 判断一个数是否为素数 def is_prime(num): if num < 2: return False for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return True # 生成小于等于n的所有素数 def generate_primes(n): primes = [] for i in range(2, n + 1): if is_prime(i): primes.append(i) return primes # 计算满足条件的数对数量 def count_pairs(n): primes = generate_primes(n) count = 0 for p in primes: for x in range(1, n + 1): for y in range(1, n + 1): if math.gcd(x, y) == p: count += 1 return count # 读取输入 n = int(input()) # 计算并输出结果 result = count_pairs(n) print(result) ``` 代码解释 1. `is_prime` 函数：用于判断一个数是否为素数。若该数小于2，则不是素数；否则，检查该数是否能被2到其平方根之间的任何整数整除，若能，则不是素数。 2. `generate_primes` 函数：用于生成小于等于 `n` 的所有素数。遍历2到 `n` 之间的所有整数，调用 `is_prime` 函数判断是否为素数，若是，则将其添加到素数列表中。 3. `count_pairs` 函数：用于计算满足条件的数对数量。对于每个素数 `p`，遍历 `x` 和 `y` 的所有可能取值，计算 `gcd(x, y)`，若 `gcd(x, y)` 等于 `p`，则将计数器加1。 4. 主程序：读取输入的整数 `n`，调用 `count_pairs` 函数计算满足条件的数对数量，并输出结果。 复杂度分析 - 时间复杂度：$O(n^2 \sqrt{n})$，其中 $n$ 是输入的整数。生成素数的时间复杂度为 $O(n \sqrt{n})$，计算数对数量的时间复杂度为 $O(n^2)$。 - 空间复杂度：$O(n)$，主要用于存储素数列表。 [2026-01-25 09:41:00 | AI问答 | 711点数解答]