我正在寻找一种找到最接近的质数的方法。无论是大于还是小于，只要最接近即可（最好不会溢出）。至于速度，如果它能在1GHz计算机上的软件中大约50毫秒内计算完成（在Linux内部运行），我将非常高兴。
在C语言中，如何找到与一个32位无符号整数最接近的质数？
12
- Erkling
7
4如何创建一个包含所有整数范围内质数的数组？ - MByD
嗯，根据从0x0到0xFFFFFFFF的质数数量，我想那可能是最合适的方法。 - Erkling
102^32以下共有203280221个质数。这样一张表大约需要800MB的存储空间。这太多了吗？ - R. Martinho Fernandes
@Erkling 对的，所以你从特定的数字开始，对该数字进行素数测试，逐渐增加直到找到一个素数，然后通过递减做同样的操作，并选择可能最接近的两个中的一个。 - nos
1考虑到机器只有256MB的RAM，因此这个程序应该尽可能小。@nos 我明白了，我想这应该是相对适合的。 - Erkling
显示剩余2条评论
2个回答
21
在范围（2^32-1）内，最大素数间隙为(335)。有(6542)个小于(2^16)的质数可以制表，并用于筛选一次性设置后的连续奇数值。显然，只需要测试小于等于候选人平方根的质数，以获得特定的候选人价值。
或者：使用SPRP基数{2,7,61}的Miller-Rabin检验的确定性变体足以证明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％的所有奇合成数。
- Brett Hale
1
这种风格可以继续使用下面的5个质数
{29, 31, 37, 41, 43}，它们的乘积是58642669。等等等等。但是每组中的质数数量会缩小，因为最终乘积将超过32位。 - Jesse Chisholm8
更新2: 修复了一些导致小n的错误答案的bug（采用了粗暴的方式）。感谢Brett Hale注意到！还添加了一些断言来记录一些假设。
更新: 我编写了这个程序，并且似乎完全足够满足您的要求（在2^29到2^32-1之间解决了1000个随机实例，耗时＜100ms，在2.2GHz的机器上-虽然不是严格的测试但仍然很有说服力）。
它是用C++编写的，因为我改编的筛子代码就是这样，但是转换成C应该很简单。内存使用也相对较小，您可以通过检查来了解情况。
由于函数调用的方式，您可以看到返回的数字是适合32位的最近质数，但实际上这是相同的，因为2^32左右的质数是4294967291和4294967311。
我试图确保没有由于整数溢出而导致的错误（因为我们处理的数字直接达到UINT_MAX）；希望我没有犯错。如果您想使用64位类型或者知道您的数字比2 ^ 32-256小，那么代码可以简化，因为您不必担心在循环条件中绕过轮廓。此外，只要您愿意计算/存储所需极限的小质数，这个想法就可以扩展到更大的数字。
我还应该注意，这些数字中小质数筛子运行得相当快（从粗略测量中可以看出需要4-5毫秒），因此如果您特别缺乏内存，则每次运行它而不是存储小质数是可行的（在这种情况下，您可能需要使mark[]数组更加空间有效）。
如果您知道小于2 ^ 16的质数（只有6542个），则可以筛选该范围内的区间；如果质数本身可能大于2 ^ 32-1，则应稍微提高一些。这不一定是最快的方法，但非常简单，而且更高级的质数测试技术确实适用于更大的范围。
基本上，使用Eratosthenes筛法获取“小”质数（例如前7000个）。显然，您只需要在程序开始时执行一次，但它应该非常快。
然后，假设您的“目标”数字为'a'，请考虑某个值n的区间[a-n/2，a+n/2)。也许n = 128是一个合理的起点；如果第一个区间中的数字都是合成数，则可能需要尝试相邻的区间。
对于每个“小”质数p，请在范围内划掉它的倍数，使用除法找到开始的位置。一个优化是，您只需要从p * p开始划掉多个（这意味着一旦p * p超过区间，您就可以停止考虑质数）。
除了前几个之外，大多数质数在区间内要么具有一个要么没有一个倍数；为了利用这一点，您可以预先忽略前几个质数的倍数。最简单的方法是忽略所有偶数，但忽略2,3和5的倍数并不罕见；这将留下模30余1,7,11,13,17,19,23和29的整数（有八个，在筛选大范围时很好地映射到字节的位）。
...有点跑题了；无论如何，一旦处理完所有小质数（直到p * p> a + n / 2），您只需在区间中查找未划掉的数字；由于您想要最靠近a的数字，请从那里开始搜索，并向两个方向搜索。
它是用C++编写的，因为我改编的筛子代码就是这样，但是转换成C应该很简单。内存使用也相对较小，您可以通过检查来了解情况。
由于函数调用的方式，您可以看到返回的数字是适合32位的最近质数，但实际上这是相同的，因为2^32左右的质数是4294967291和4294967311。
我试图确保没有由于整数溢出而导致的错误（因为我们处理的数字直接达到UINT_MAX）；希望我没有犯错。如果您想使用64位类型或者知道您的数字比2 ^ 32-256小，那么代码可以简化，因为您不必担心在循环条件中绕过轮廓。此外，只要您愿意计算/存储所需极限的小质数，这个想法就可以扩展到更大的数字。
我还应该注意，这些数字中小质数筛子运行得相当快（从粗略测量中可以看出需要4-5毫秒），因此如果您特别缺乏内存，则每次运行它而不是存储小质数是可行的（在这种情况下，您可能需要使mark[]数组更加空间有效）。
#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 ^ 32-1，则应稍微提高一些。这不一定是最快的方法，但非常简单，而且更高级的质数测试技术确实适用于更大的范围。
基本上，使用Eratosthenes筛法获取“小”质数（例如前7000个）。显然，您只需要在程序开始时执行一次，但它应该非常快。
然后，假设您的“目标”数字为'a'，请考虑某个值n的区间[a-n/2，a+n/2)。也许n = 128是一个合理的起点；如果第一个区间中的数字都是合成数，则可能需要尝试相邻的区间。
对于每个“小”质数p，请在范围内划掉它的倍数，使用除法找到开始的位置。一个优化是，您只需要从p * p开始划掉多个（这意味着一旦p * p超过区间，您就可以停止考虑质数）。
除了前几个之外，大多数质数在区间内要么具有一个要么没有一个倍数；为了利用这一点，您可以预先忽略前几个质数的倍数。最简单的方法是忽略所有偶数，但忽略2,3和5的倍数并不罕见；这将留下模30余1,7,11,13,17,19,23和29的整数（有八个，在筛选大范围时很好地映射到字节的位）。
...有点跑题了；无论如何，一旦处理完所有小质数（直到p * p> a + n / 2），您只需在区间中查找未划掉的数字；由于您想要最靠近a的数字，请从那里开始搜索，并向两个方向搜索。
- Sumudu Fernando
8
如果Brett Hale在最大间隙方面是正确的，那么你的“n”应该是335，或者可能再大几个。 - Mark Ransom
此外，我将预先计算出2^16以下的质数，存储在静态表中，并在
a足够小的情况下使用二分查找。 - Mark Ransom二分查找是个好主意（我没说“静态表”，但那确实是我的意思）。我不知道最大间隔有多常见，所以在平均情况下使用小于335的n然后在需要时测试相邻区间可能更好（虽然128和512的差别可能微乎其微；我用这种构造方法建立了一个通用的分段筛法，并发现大小约为20000的间隔性能良好）。 - Sumudu Fernando
我怀疑筛选过程将是这个过程中最慢的部分，需要在两个不同的间隔上进行两次筛选将是一件遗憾的事情。第一次就确保好会更好。 - Mark Ransom
输入数字 '3' 会告诉我最近的质数是 '1'，而输入数字 '13' 则会给出 '23'。 - Brett Hale
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接