用C++解决“两质整数”区间询问问题

以下是解决该问题的C++代码： ```cpp #include <iostream> #include <vector> using namespace std; const int MAXN = 1e6 + 5; // 标记质数 vector<bool> isPrime(MAXN, true); // 标记两质整数 vector<bool> isTwoPrimeProduct(MAXN, false); // 前缀和数组，用于快速计算区间内两质整数的数量 vector<int> prefixSum(MAXN, 0); // 埃拉托斯特尼筛法找出质数 void sieve() { isPrime[0] = isPrime[1] = false; for (int i = 2; i * i < MAXN; i++) { if (isPrime[i]) { for (int j = i * i; j < MAXN; j += i) { isPrime[j] = false; } } } // 找出所有两质整数 for (int i = 2; i < MAXN; i++) { if (isPrime[i]) { for (int j = i; j < MAXN; j++) { if (isPrime[j]) { long long product = (long long)i * j; if (product < MAXN) { isTwoPrimeProduct[product] = true; } else { break; } } } } } // 计算前缀和 for (int i = 1; i < MAXN; i++) { prefixSum[i] = prefixSum[i - 1] + isTwoPrimeProduct[i]; } } int main() { sieve(); int Q; cin >> Q; for (int i = 0; i < Q; i++) { int L, R; cin >> L >> R; // 利用前缀和计算区间内两质整数的数量 cout << prefixSum[R] - prefixSum[L - 1] << endl; } return 0; } ``` ### 代码解释： 1. **质数筛法**：使用埃拉托斯特尼筛法找出所有小于`MAXN`的质数，标记在`isPrime`数组中。 2. **找出两质整数**：遍历所有质数对，计算它们的乘积，如果乘积小于`MAXN`，则标记该数为两质整数，存储在`isTwoPrimeProduct`数组中。 3. **前缀和计算**：使用前缀和数组`prefixSum`记录每个位置之前的两质整数的数量，方便快速计算任意区间内两质整数的数量。 4. **处理询问**：对于每个询问`[L, R]`，通过前缀和数组计算区间内两质整数的数量，即`prefixSum[R] - prefixSum[L - 1]`。 ######[AI问答 | 685点数解答 | 2026-04-19 16:15:04]