c++ 素数方阵 包河区

### C++ 素数方阵问题的实现 在编程竞赛中，素数方阵问题通常要求将前 $ n^2 $ 个素数按照某种特定的螺旋方式填入一个 $ n \times n $ 的矩阵中，并根据给定的坐标输出对应的素数值。这类问题常见于算法竞赛或区域性编程比赛（如包河区相关赛事）。 #### 算法思路 1. **判断素数**：使用高效的素数判断函数 `is_prime(int n)`，通过遍历从 2 到 $ \sqrt{n} $ 的所有整数来检查是否存在因子。 2. **生成素数序列**：构建一个包含前 $ n^2 $ 个素数的数组或向量。 3. **填充素数方阵**：按照顺时针螺旋的方式将素数依次填入矩阵中。 4. **查询指定位置的值**：根据输入的坐标返回矩阵中的对应元素。 #### 示例代码实现 以下是一个完整的 C++ 实现方案： ```cpp #include <iostream> #include <vector> #include <cmath> using namespace std; typedef long long ll; // 判断一个数是否为素数 bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; } // 生成前 n^2 个素数 vector<ll> generate_primes(int n) { vector<ll> primes; int count = 0; int num = 2; while (count < n * n) { if (is_prime(num)) { primes.push_back(num); count++; } num++; } return primes; } // 构建素数方阵并填充 ll build_prime_square(int n, int x, int y) { vector<ll> primes = generate_primes(n); ll matrix[21][21] = {0}; int top = 0, bottom = n - 1, left = 0, right = n - 1; int index = 0; // 螺旋填充矩阵 while (top <= bottom && left <= right) { for (int i = left; i <= right; i++) { matrix[top][i] = primes[index++]; } top++; for (int i = top; i <= bottom; i++) { matrix[i][right] = primes[index++]; } right--; if (top <= bottom) { for (int i = right; i >= left; i--) { matrix[bottom][i] = primes[index++]; } bottom--; } if (left <= right) { for (int i = bottom; i >= top; i--) { matrix[i][left] = primes[index++]; } left++; } } // 返回指定坐标的值（注意题目中的坐标是从1开始） return matrix[x - 1][y - 1]; } int main() { int n, x, y; cin >> n >> x >> y; cout << build_prime_square(n, x, y) << endl; return 0; } ``` #### 代码说明 - **`is_prime(int n)`**：用于判断一个整数是否为素数。该函数通过检查从 2 到 $ \sqrt{n} $ 的范围内是否有因数来确定结果。 - **`generate_primes(int n)`**：生成前 $ n^2 $ 个素数，并存储在一个向量中。 - **`build_prime_square(int n, int x, int y)`**：创建一个大小为 $ n \times n $ 的矩阵，并按照螺旋顺序填入素数。最后返回指定坐标处的值。 #### 时间复杂度分析 - 素数判断的时间复杂度为 $ O(\sqrt{n}) $。 - 生成 $ n^2 $ 个素数的总时间复杂度约为 $ O(n^2 \cdot \sqrt{m}) $，其中 $ m $ 是最大的素数。 - 填充矩阵的时间复杂度为 $ O(n^2) $。 #### 应用场景 该算法适用于编程竞赛、数学矩阵构造以及需要高效生成和排列素数的问题。 ---