我正在寻找一种找到最接近素数的方法。大于或小于，这并不重要，只是最接近的（最好不要溢出。）至于速度，如果它能在1GHz的机器上（在软件中，在Linux中运行）在大约50毫秒内计算出来，我会欣喜若狂。
在（2^32-1）之前的范围内的最大素数差距是（335）。有（6542）个小于（2^16）的素数可以制成表格，并用于在一次性设置后筛选连续的奇数值。显然，只有素数<=floor（sqrt（候选者））需要针对特定的候选者值进行测试。
或者：Miller Rabin检验的确定性变体，具有SPRP基：{2，7，61}，足以证明32位值的素性。由于测试的复杂性（需要求幂等），我怀疑它对这么小的考生来说会这么快。
编辑：实际上，如果乘方/减方可以保持在32位（可能需要64位支持），M-R测试可能会更好。主要间隙通常会小得多，从而使筛网设置成本过高。如果没有大型查找表等，您还可以从更好的缓存位置获得提升。
此外：素数{2，3，5，7，11，13，17，19，23}的乘积=（223092870）。明确测试[2，23]中的任何候选项。计算最大公约数：g = gcd(u, 223092870UL)。如果是(g != 1)，则候选是复合的。如果(g == 1 && u < (29 * 29))，则候选（u > 23）肯定是素数。否则，继续进行更昂贵的测试。使用32位算术的单个gcd测试非常便宜，根据Mertens（？）定理，这将检测到约68.4%的所有奇数。
UPDATE 2：修复了（以严厉的方式）一些导致小n错误答案的错误。感谢Brett Hale的注意！还添加了一些断言来记录一些假设。
更新：我对它进行了编码，它似乎足够快，可以满足您的需求（在2.2GHz的机器上，以<100ms的时间解决了[2^29，2^32-1]中的1000个随机实例——这不是一个严格的测试，但仍然令人信服）。
它是用C++编写的，因为这就是我的sive代码（我改编自它），但转换为C应该很简单。内存使用量也（相对）较小，您可以通过检查看到这一点。
你可以看到，由于函数的调用方式，返回的数字是最接近的素数，适合32位，但事实上这是一样的，因为2^32周围的素数是4294967291和4294967311。
我试着确保不会因为整数溢出而出现任何错误（因为我们处理的是一直到UINT_MAX的数字）；希望我没有犯错误。如果你想使用64位类型（或者你知道你的数字会小于2^32-256），代码可以简化，因为你不必担心循环中的情况。此外，只要你愿意计算/存储小素数到所需的极限，这个想法就可以扩展到更大的数字。
我还应该注意到，小素数筛对这些数字运行得很快（粗略测量4-5毫秒），所以如果你特别缺乏内存，每次运行它而不是存储小素数是可行的（在这种情况下，你可能想让标记[]阵列更节省空间）
#include <iostream>
#include <cmath>
#include <climits>
#include <cassert>
using namespace std;
typedef unsigned int UI;
const UI MAX_SM_PRIME = 1 << 16;
const UI MAX_N_SM_PRIMES = 7000;
const UI WINDOW = 256;
void getSMPrimes(UI primes[]) {
UI pos = 0;
primes[pos++] = 2;
bool mark[MAX_SM_PRIME / 2] = {false};
UI V_SM_LIM = UI(sqrt(MAX_SM_PRIME / 2));
for (UI i = 0, p = 3; i < MAX_SM_PRIME / 2; ++i, p += 2)
if (!mark[i]) {
primes[pos++] = p;
if (i < V_SM_LIM)
for (UI j = p*i + p + i; j < MAX_SM_PRIME/2; j += p)
mark[j] = true;
}
}
UI primeNear(UI n, UI min, UI max, const UI primes[]) {
bool mark[2*WINDOW + 1] = {false};
if (min == 0) mark[0] = true;
if (min <= 1) mark[1-min] = true;
assert(min <= n);
assert(n <= max);
assert(max-min <= 2*WINDOW);
UI maxP = UI(sqrt(max));
for (int i = 0; primes[i] <= maxP; ++i) {
UI p = primes[i], k = min / p;
if (k < p) k = p;
UI mult = p*k;
if (min <= mult)
mark[mult-min] = true;
while (mult <= max-p) {
mult += p;
mark[mult-min] = true;
}
}
for (UI s = 0; (s <= n-min) || (s <= max-n); ++s)
if ((s <= n-min) && !mark[n-s-min])
return n-s;
else if ((s <= max-n) && !mark[n+s-min])
return n+s;
return 0;
}
int main() {
UI primes[MAX_N_SM_PRIMES];
getSMPrimes(primes);
UI n;
while (cin >> n) {
UI win_min = (n >= WINDOW) ? (n-WINDOW) : 0;
UI win_max = (n <= UINT_MAX-WINDOW) ? (n+WINDOW) : UINT_MAX;
if (!win_min)
win_max = 2*WINDOW;
else if (win_max == UINT_MAX)
win_min = win_max-2*WINDOW;
UI p = primeNear(n, win_min, win_max, primes);
cout << "found nearby prime " << p << " from window " << win_min << ' ' << win_max << 'n';
}
}
如果你知道2^16以内的素数，你可以筛选这个范围内的区间（只有6542<=2^16；如果素数本身可以大于2^32-1，你应该更高一点）。不一定是最快的方法，但非常简单，更花哨的初级测试技术确实适用于更大的范围。
基本上，做一次Eratosthenes的常规筛选，得到"小"素数（比如前7000个）。显然，你只需要在程序开始时做一次，但应该非常快。
然后，假设你的"目标"数字是"a"，考虑n的某个值的区间[a-n/2，a+n/2）。可能n=128是一个合理的起点；如果第一个区间中的数字都是复合的，你可能需要尝试相邻的区间。
对于每一个"小"素数p，划掉它在该范围内的倍数，用除法找到起点。一个优化是，你只需要开始划掉从p*p开始的倍数（这意味着一旦p*p高于区间，你就可以停止考虑素数）。
除前几个素数外，大多数素数在区间内都有一个或零个倍数；为了利用这一点，你可以预先忽略前几个素数的倍数。最简单的方法是忽略所有偶数，但忽略2、3和5的倍数并不罕见；这留下了与1、7、11、13、17、19、23和29 mod 30全等的整数（有八个，在筛选大范围时很好地映射到字节的位）。
有点偏离了切线；无论如何，一旦你处理了所有的小素数（直到p*p>a+n/2），你只需要在区间中寻找没有划掉的数字；因为你想要一个最接近的开始看那里，并向外搜索两个方向。