实现素数哈希时获取与桶数n最接近素数的最优方法是什么？

素数作为哈希表桶数是非常经典的工程优化，靠取模运算打散哈希值的效果比2的整数次幂桶数对低质量哈希函数更友好，属于你提到的典型quick and dirty方案。

首先要先纠正一个常见的实现误区：埃拉托斯特尼筛法的O(n loglogn)复杂度是面向批量生成[2,n]区间所有素数场景的，而你的需求只是找n附近的单个素数（哈希表扩容场景下一般找大于等于n的最小素数即可，不会找更小的，否则桶容量不足），直接用筛法属于典型的杀鸡用牛刀，实际效率远低于针对性的方案，可选的更优实现按实用性排序如下：

工程首选：预生成素数查表法（O(1)时间开销） #

• 几乎所有工业级标准库的哈希表实现，都不会在运行时动态计算素数，而是提前硬编码一组按固定倍率（1.5~2倍）增长的素数序列，覆盖从个位数到2^32甚至264范围的所有常用桶数，扩容时直接二分找第一个大于目标容量的素数即可，没有任何运行时计算开销。
• 这种方案的实现成本极低，只需要提前存几十个素数就能覆盖99.9%的业务场景，下面是一组经过验证的常用扩容素数序列：
  [7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899, 701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557, 359339171, 718678369, 1437356741, 2874713497]

超大容量场景：逐数素性检测法 #

• 如果你的哈希表需要支持远超预生成表覆盖范围的超大桶数，直接从目标n开始向上遍历（跳过所有偶数，除2外所有素数都是奇数，直接砍掉一半计算量），对每个数做素性检测，第一个通过检测的数就是你要的目标素数。
• 素性检测不要用朴素的全范围试除法：
  • 数值小于1e6的时候，用优化版试除法足够快：先试除3、5、7、11、13这些小素数，再遍历到sqrt(k)即可，实际耗时极低。
  • 数值大于1e6的时候直接用米勒-拉宾（Miller-Rabin）素性检测，这是目前工业界通用的大素数判定方案：它本质是概率性检测，但只要选定固定的检测基，在确定数值范围内可以做到100%准确，比如判定小于2^64的数，只需要用[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]这12个基做检测，完全不会出现误判。
  • 米勒-拉宾的单个数检测复杂度是O(k log³n)，k是检测基的数量，再加上素数之间的平均间隔只有O(log n)，整体找素数的开销远低于埃氏筛，n越大优势越明显，而且不需要像筛法那样申请大块连续内存存标记，内存开销可以忽略。

补充提醒：不管是埃氏筛还是线性欧拉筛，都只适合需要批量获取大段区间素数的场景，单找某一个值附近的素数时，筛法的时间和内存开销都是完全没必要的。

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