如何在1秒内找出10^9范围内数组的第二大质数？

一、核心问题：快速判断1e9以内的数是否为质数 #

你之前用的埃氏筛不适合1e9范围——筛到1e9需要的时间和内存都远超限制；普通试除法对1e6个元素来说，最坏情况（每个数都是接近1e9的质数）会有1e6 * 3e4 = 3e10次操作，肯定超时。这里推荐用确定性米勒-拉宾素性测试，针对1e9以内的数，只需要固定几个基就能100%准确判断，速度极快。

米勒-拉宾的确定性实现（针对1e9）

对于所有小于1e9的整数，用基{2, 3, 5, 7, 11}进行测试就足够覆盖所有合数。步骤大致是：

• 处理特殊值：小于2的数不是质数；2是唯一的偶质数；大于2的偶数直接排除。
• 将目标数n分解为n-1 = d*2^s的形式。
• 对每个基a，计算x = a^d mod n：
  • 如果x == 1或x == n-1，则继续下一个基。
  • 否则重复s-1次平方x，如果某次得到n-1则继续下一个基，否则n是合数。
• 所有基测试通过则n是质数。

这个方法每个数的判断次数固定为5次左右，1e6个元素总操作数仅5e6次，完全符合1秒时间限制。

二、遍历数组维护前两大质数 #

不需要先收集所有质数再排序（排序1e6元素虽然快，但不如边遍历边维护高效），直接在遍历过程中跟踪最大和第二大质数：

• 初始化max1（最大质数）和max2（第二大质数）为-1（或其他无效标记）。
• 遍历数组每个元素num：
  1. 如果num <= max2，直接跳过（不可能成为前二质数，节省判断时间）。
  2. 判断num是否为质数：
     • 若不是质数，跳过。
     • 若是质数：
       • 如果num > max1：将max2更新为max1，max1更新为num。
       • 否则如果num > max2且num != max1：将max2更新为num（避免重复的最大质数覆盖第二大）。
• 遍历结束后，若max2仍为无效值，说明数组中质数个数不足2；否则max2就是答案。

额外优化点 #

• 先过滤偶数：除了2之外，所有偶数直接跳过质数判断，减少一半的判断量。
• 提前终止：如果遍历过程中已经找到前两大质数（比如max1是1e9以内最大质数999999937，max2是次大的999999929），后续所有小于等于max2的数都可以直接跳过，进一步节省时间。

内容的提问来源于stack exchange，提问作者Nguyễn Việt Hưng