C++实现计算指定区间内“两质整数”数量的程序

以下是为你补全的代码： ```cpp #include <bits/stdc++.h> using namespace std; bool isnp[1000005], vis[1000005]; int p[1000005], sum[1000005], m; // 埃拉托斯特尼筛法初始化质数数组 void init() { m = 0; for (int i = 2; i <= 1e6; i++) { if (!isnp[i]) { m++; // 将质数存到p数组中 p[m] = i; for (int j = i + i; j <= 1e6; j += i) { // 将i的倍数标记为非质数 isnp[j] = true; } } } } int main() { init(); // 预处理出1e6以内的两质整数 for(int i = 1; i <= m; i++) { for(int j = 1; j <= i; j++) { long long product = (long long)p[i] * p[j]; if(product > 1e6) break; vis[product] = true; // 标记为两质整数 } } // 计算前缀和 1~i 之间有多少个两质整数 for(int i = 1; i <= 1e6; i++) { sum[i] = sum[i - 1]; if(vis[i]) sum[i]++; } // 处理Q次询问 int Q, L, R; cin >> Q; while(Q--) { cin >> L >> R; // 利用前缀和计算区间内两质整数的数量 cout << sum[R] - sum[L - 1] << endl; } return 0; } ``` ### 代码解释： - **`init`函数**：使用埃拉托斯特尼筛法找出 $1$ 到 $10^6$ 之间的所有质数，并将它们存储在数组`p`中，同时标记非质数。 - **预处理两质整数**：通过双重循环遍历所有质数对，计算它们的乘积。如果乘积在 $1$ 到 $10^6$ 范围内，则将其标记为两质整数。 - **计算前缀和**：使用数组`sum`来记录 $1$ 到 $i$ 之间两质整数的数量。 - **处理询问**：对于每次询问 $[L, R]$，通过前缀和数组计算该区间内两质整数的数量，即`sum[R] - sum[L - 1]`。 ######[AI问答 | 666点数解答 | 2026-08-15 20:35:19]