哈希场景下如何找到大于定值的素数？时间复杂度是多少？

在通用哈希这类场景中，我们需要找到一个大于待映射元素数量的素数p，常用的查找方法和时间复杂度如下：

一、素数查找方法 #

1. 试除法（适合中小规模场景） #

从目标值n的下一个整数开始遍历：

• 若n是偶数，直接从n+1开始；若n是奇数，从n+2开始（跳过偶数，减少一半检查量）
• 对每个候选数p，检查它是否能被2到√p之间的任意整数整除：
  • 若所有数都无法整除p，则p就是我们要找的素数
  • 若存在能整除的数，直接跳过该候选数，检查下一个

2. 米勒-拉宾素性测试（适合大规模场景） #

当待映射元素数量极大，试除法效率不足时，用这个概率性素性测试（误判概率极低，完全满足哈希场景需求）：

• 选取几个小素数作为测试基（比如2、3、5、7），对候选数p进行多轮测试
• 核心步骤：
  1. 将p-1分解为d*2^s的形式
  2. 对每个基a，计算x = a^d mod p
  3. 若x == 1或x == p-1，则通过该基的测试；否则反复对x进行平方操作（最多s-1次），若某次得到p-1则通过，否则判定p为合数

二、时间复杂度分析 #

试除法 #

• 平均时间复杂度：O(√n)，其中n是我们设定的最小阈值（待映射元素数量）。因为平均来看，n附近的素数间隙约为log n，每个候选数的检查需要遍历到√p（p和n量级相近），整体复杂度可简化为O(√n)
• 最坏情况：若遇到罕见的大素数间隙，耗时会增加，但哈希场景中基本不会碰到这种极端情况，实际使用足够高效

米勒-拉宾素性测试 #

• 若进行k轮测试，时间复杂度为O(k log³n)。其中log³n来自模幂运算的计算成本，k是测试基的数量（通常取3-5个即可保证正确性）
• 这种方法的效率远高于试除法，非常适合处理待映射元素数量极大的场景

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