一种在C中找到无符号长整数(32位宽)的最接近素数的方法?

我正在寻找一种方法来找到最接近的素数。 大于或小于,无关紧要,只是最接近(没有溢出,最好是。)至于速度,如果它可以在1GHz机器上大约50毫秒计算它(在软件中,在Linux内运行),我会欣喜若狂。

更新2 :修复(以严厉的方式)一些错误导致小n的错误答案。 感谢Brett Hale的注意! 还添加了一些断言来记录一些假设。

更新 :我对此进行了编码,看起来足够快,满足您的要求(在2.2GHz机器上,在<100ms内从[2 ^ 29,2 ^ 32-1]解决了1000个随机实例 - 不是一个严格的测试,但仍然令人信服)。

它是用C ++编写的,因为那是我的筛选代码(我改编自它)所在,但转换为C应该是直截了当的。 内存使用量也相对较小,您可以通过检查看到。

你可以看到,由于调用函数的方式,返回的数字是最接近32位的素数,但实际上这是相同的,因为2 ^ 32周围的素数是4294967291和4294967311。

我试图确保整数溢出不会有任何错误(因为我们处理的数字直到UINT_MAX); 希望我没有在那里犯错。 如果您想使用64位类型(或者您知道您的数字小于2 ^ 32-256),则可以简化代码,因为您不必担心在循环条件中回绕。 只要您愿意计算/存储小素数达到所需限制,这个想法也可以扩展到更大的数字。

我还应该注意到,这些数字的小素数筛子运行得非常快(粗略测量时间为4-5毫秒),所以如果你特别缺乏记忆,那么每次运行它而不是存储小素数是可行的(你在这种情况下,我可能想让mark []数组更节省空间)

#include  #include  #include  #include  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[ns-min]) return ns; 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值的区间[an / 2,a + n / 2]。 可能n = 128是一个合理的起点; 如果第一个中的数字都是复合的,您可能需要尝试相邻的间隔。

对于每个“小”素数p,在该范围内划掉它的倍数,使用除法找到从哪里开始。 一个优化是你只需要开始从p * p开始交叉多次(这意味着一旦p * p高于区间,你可以停止考虑质数)。

除前几个之外的大多数素数将在区间内具有一个或零个倍数; 利用这个你可以预先忽略前几个素数的倍数。 最简单的方法是忽略所有偶数,但忽略2,3和5的倍数并不罕见; 这使整数与1,7,11,13,17,19,23和29 mod 30一致(有8个,当筛选大范围时,它很好地映射到一个字节的位)。

......有点像切线那样; 无论如何,一旦你处理了所有小素数(直到p * p> a + n / 2),你只需查看你没有交叉的数字的间隔; 因为你想要最接近一个开始看那里并向两个方向向外搜索。

在(2 ^ 32 – 1)范围内最大的主要差距是(335)。 有(6542)个小于(2 ^ 16)的质数可以制表并用于在一次性设置后筛选连续的奇数值。 显然,只需要针对特定​​候选值测试素数<= floor(sqrt(候选者))。

或者: Miller-Rabin检验的确定性变体 ,SPRP碱基:{2,7,61}足以certificate32位值的原始性。 由于测试的复杂性(需要取幂等),我怀疑它对于这样的小候选者来说会快得多。

编辑:实际上,如果乘法/减少可以在求幂时保持32位(可能需要64位支持),MR测试可能会更好。 主要间隙通常会小得多,使得筛网设置成本过高。 如果没有大型查找表等,您可能还会从更好的缓存位置获得提升。

此外:素数的乘积{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%。