如何优化10^6规模数组逐元素素数判定的运行性能

针对输入慢、素数判定慢两个问题，直接按以下方案调整即可：

输入环节优化 #

默认cin同步了C标准IO接口、且绑定了cout，速度极慢，在main函数最开头加入两行代码即可让cin速度达到和scanf相当的水平，完全覆盖1e6规模的输入需求：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 后续写入你的原有业务逻辑
}

如果追求极致速度，可以手写基于getchar的快读函数，1e6数据量下上述优化已经足够，不需要额外改动。

素数判定环节优化 #

逐个数调用素数检测函数的逻辑，哪怕算法优化到极致，在1e6规模下效率也远低于筛法，根据数组元素的取值范围选对应方案即可：

• 数组元素最大值不超过1e7时：优先用线性筛（欧拉筛）预处理出取值范围内所有数的素数标记，后续直接查表输出结果，1e6规模下预处理加查询总耗时不到1ms，比逐点判定快两个数量级以上。
  可直接复用的线性筛代码：

  #include <vector>
  std::vector<bool> build_prime_table(int max_num) {
      std::vector<bool> is_prime(max_num + 1, true);
      std::vector<int> prime_list;
      is_prime[0] = is_prime[1] = false;
      for (int i = 2; i <= max_num; ++i) {
          if (is_prime[i]) {
              prime_list.push_back(i);
          }
          for (int p : prime_list) {
              if (1LL * i * p > max_num) break;
              is_prime[i * p] = false;
              if (i % p == 0) break;
          }
      }
      return is_prime;
  }
  

  使用逻辑：先遍历一次输入数组找到元素最大值，调用上述函数拿到素数标记表，之后再遍历一次输入数组，直接查表就能得到每个位置对应的素数判定结果，不需要重复做计算。
• 数组元素最大值远大于1e7（如超过1e9）时：筛法会占用过多内存，此时改用固定基底的Miller-Rabin素性检测即可，针对32位整数范围，使用{2,3,5,7,11,13,17,19,23,29,31,37}作为检测基底可以保证结果100%准确，单个数检测为常数级耗时，比普通试除法快数十倍。

额外性能提示 #

• 素数标记优先用vector<bool>存储，它是位压缩实现，1e6个标记仅占约125KB内存，缓存命中率远高于普通数组，运行速度更快。
• 如果坚持用试除法做单个数判定，只需要遍历到sqrt(n)即可终止，且可以预先跳过所有偶数，直接减少一半计算量。

内容的提问来源于stack exchange，提问作者Lê Trần Nam Khánh