#include <bits/stdc++.h> using namespace std; void sieve(long long maxVal, vector<int>& primes) { // 创建布尔数组标记非素数位置 bool isNotPrime[maxVal+1]; memset(isNotPrime, 0, sizeof(bool)*(maxVal+1)); for (long long p=2; p*p<=maxVal; ++p){ if (!isNotPrime[p]){ for (long long multiple=p*p; multiple<=maxVal; multiple+=p) isNotPrime[multiple] = true; } } for (long long p=2; p<=maxVal; ++p){ if(!isNotPrime[p]) primes.push_back(p); } } int main(){ ios::sync_with_stdio(false); // 加速输入输出流操作 cin.tie(NULL); long long m,n; cin>>m>>n; if(m >n ){ swap(m,n); } long long MAX_VAL=(n>m?n:m)+1; vector<int>primesList; sieve(MAX_VAL-1 ,primesList); auto lowerIt =lower_bound(primesList.begin(),primesList.end(),m ); auto upperIt =upper_bound(lowerIt ,primesList.end(),n ); cout<<distance(lowerIt,upperIt)<<endl; return 0; }这段代码Memory Exceeded了，请优化到满分

这段代码的主要功能是从区间 `[m, n]` 中统计所有素数的数量，并通过埃拉托色尼筛法生成素数表。然而，由于 `bool isNotPrime[maxVal+1]` 数组占用大量内存空间，在较大的范围内可能会导致 **Memory Exceeded** 的错误。 以下是针对该问题的具体优化方案： --- ### 1. 使用位运算代替布尔数组 原代码中的 `bool isNotPrime[maxVal+1]` 每个元素占用了 1 字节的空间。我们可以通过位运算将每个标志压缩至单比特存储，从而减少约 8 倍的内存消耗。 修改后的核心部分如下： ```cpp // 定义一个位向量来替代原来的 bool 数组 vector<bool> isNotPrime((maxVal + 7) / 8, false); inline void set_bit(int idx, vector<bool>& vec) { // 设置第 idx 位为 true int byte_idx = idx / 8; char bit_mask = 1 << (idx % 8); vec[byte_idx] |= bit_mask; } inline bool get_bit(int idx, const vector<bool>& vec) { // 获取第 idx 位的状态 int byte_idx = idx / 8; char bit_mask = 1 << (idx % 8); return (vec[byte_idx] & bit_mask) != 0; } ``` 然后调整循环内的逻辑： ```cpp for (long long p = 2; p * p <= maxVal; ++p) { if (!get_bit(p, isNotPrime)) { for (long long multiple = p * p; multiple <= maxVal; multiple += p) set_bit(multiple, isNotPrime); } } ``` 最后遍历的时候也改为按位判断： ```cpp for (long long p = 2; p <= maxVal; ++p) { if (!get_bit(p, isNotPrime)) primes.push_back(p); } ``` --- ### 2. 减小筛选范围（分段筛） 当 `n - m` 较大而 `m` 和 `n` 都很大时，可以采用“分块”技术——即只对需要的部分进行计算而不是从头开始构建整个素数列表。 我们可以先用较小规模的标准埃氏筛获取 sqrt(n) 内的所有质因子集合 F；之后再利用这些因子快速标记出目标区间的合数状态即可。 示例如下： #### 第一步：预处理 √MAX 范围内所有素数 ```cpp const int MAX_SQRT = 5e4 + 5; // 根据题目数据设定适当大小值sqrt(MAX_VAL) vector<int> smallPrimes; sieve(sqrt(maxVal), smallPrimes); // 只算到根号处 ``` #### 第二步：逐段扫描并计数 假设每一段长度设为 BLOCK_SIZE=1e6 左右，则总共需划分 ceil( (n-m)/BLOCK_SIZE ) 次迭代完成全部任务。 完整版伪码片段如下所示： ```cpp while(current_start<m){ current_start+=BLOCK_SIZE; } current_end=min(current_start+BLOCK_SIZE-1,n); // 对当前窗口做标记... memset(block_is_not_prime,0,sizeof(bool)*block_size); foreach prime in smallPrimes{ start=max(prime*prime,current_start-(current_start%prime)); while(start<=current_end && start>=current_start ){ block_is_not_prime[start-current_start]=true; start=start+prime; } } // 记录有效结果.... for(i=current_start;i<=current_end;i++)if(!block_is_not_prime[i-current_start])count++; ``` 最终汇总得到答案 count 即为目标区间 [m,n] 区间内素数总个数。 --- ### § 相关问题 § : 1. 如何进一步提升程序运行速度？ 2. 分段筛适合解决哪些特定场景下的问题？ 3. 如果输入规模非常巨大，是否还有其他更优算法可以选择？