我正在寻找一种方法来找到最接近的素数。大于或小于，没关系，只是最接近的（最好不要溢出。）至于速度，如果它可以在 1GHz 机器上大约 50 毫秒内计算出来（在软件中，在 Linux 中运行），我会欣喜若狂。
The 最大素数差距 http://primes.utm.edu/notes/GapsTable.html在 (2^32 - 1) 范围内为 (335)。可以将小于 (2^16) 的 (6542) 个素数制成表格，并用于在一次性设置后筛选连续的奇数。显然，只有素数
或者： The Miller-Rabin 检验的确定性变体 http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test，以 SPRP 为底：{2, 7, 61} 足以证明 32 位值的素性。由于测试的复杂性（需要求幂等），我怀疑对于如此小的候选人来说它是否会那么快。
Edit:实际上，如果求幂时乘法/归约可以保持为 32 位（可能需要 64 位支持），那么 M-R 测试可能会更好。主要间隙通常会小得多，使得筛子的安装成本过高。如果没有大型查找表等，您也可能会从更好的缓存局部性中获得提升。
此外：素数 {2, 3, 5, 7, 11, 13, 17, 19, 23} 的乘积 = (223092870)。显式测试 [2, 23] 中的任何候选者。计算最大公约数：g = gcd(u, 223092870UL). If (g != 1)，候选人是复合的。如果(g == 1 && u < (29 * 29))，候选人（u > 23) 绝对是素数。否则，请继续进行更昂贵的测试。使用 32 位算术的单个 gcd 测试非常便宜，根据 Mertens (?) 定理，这将检测到约 68.4%all奇合数。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
