如何编写程序找出100到10000范围内素数最多的百数区间

百区间分组规则 #

• 100到10000的百区间左端点从100开始，每次递增100，直到9900，对应右端点为左端点+100，刚好覆盖所有[100,200)、[200,300)...[9900,10000]的分组
• 用循环生成区间的伪代码参考：

  for (i = 0; i < 99; i++) {
    start = 100 + i * 100;
    end = start + 100;
    // 处理当前[start, end)区间
  }
  

  如果你现有的素数统计函数是闭区间逻辑，把end改成start + 99即可，不影响整体流程。

遍历统计步骤 #

• 初始化两个变量：max_prime_count记录当前找到的最大素数数量，初始值设为0；result_intervals记录素数最多的区间列表，初始为空。
• 遍历每一个百区间：
  • 调用你已有的素数统计函数，传入当前区间的起止值，得到当前区间的素数数量current_count
  • 对比current_count和max_prime_count：
    • 若current_count > max_prime_count：更新max_prime_count为current_count，清空result_intervals后把当前区间存入
    • 若current_count == max_prime_count：直接把当前区间追加到result_intervals中，处理并列最多的情况
• 遍历完成后，result_intervals里存的就是素数数量最多的所有区间。

可选优化方案 #

如果要提升运行效率，可以先通过埃氏筛一次性生成100到10000的所有素数，再遍历素数列表按百位分组计数，比每次单独调用区间统计函数的性能高很多，范围越大优势越明显。

内容的提问来源于stack exchange，提问作者Dean