找到最近的素数在C无符号长整型（32位宽）的方法吗？ [英] A way to find the nearest prime number to an unsigned long integer ( 32 bits wide ) in C?

问题描述

我正在寻找一种方式来找到最接近的素数。大于或小于，也没关系，只需将最接近（无pferably溢出，$ P $）。至于速度，如果它可以在大约50毫秒计算它1GHz的机器上（在软件，内部运行Linux），我会欣喜若狂。

I'm looking for a way to find the closest prime number. Greater or less than, it doesn't matter, simply the closest ( without overflowing, preferably. ) As for speed, if it can compute it in approximately 50 milliseconds on a 1GHz machine ( in software, running inside Linux ), I'd be ecstatic.

推荐答案

更新2 ：固定（在一个粗重的方式）一些bug导致错误答案的小样本。感谢布雷特硬朗的察觉！还添加了一些断言来记录一些假设。

UPDATE 2: Fixed (in a heavy-handed way) some bugs that caused wrong answers for small n. Thanks to Brett Hale for noticing! Also added some asserts to document some assumptions.

更新：I codeD这件事，它似乎足够快足够满足您的要求（上述＆lt解决了1000个随机实例从[2 ^ 29，2 ^ 32-1] 100毫秒，没有严格的测试，但仍然有说服力）

UPDATE: I coded this up and it seems plenty fast enough for your requirements (solved 1000 random instances from [2^29, 2^32-1] in <100ms, on a 2.2GHz machine -- not a rigorous test but convincing nonetheless).

这是写在C ++，因为这就是我的筛code（这是我改编自）是，但转换到C应该是简单的。内存使用率也（相对）小的，你可以通过检查看到的。

It is written in C++ since that's what my sieve code (which I adapted from) was in, but the conversion to C should be straightforward. The memory usage is also (relatively) small which you can see by inspection.

您可以看到，因为函数被调用的方式，返回的数字是，适合在32位最近的黄金，但实际上这是同一个东西，因为周围的素数2 ^ 32 4294967291和4294967311.

You can see that because of the way the function is called, the number returned is the nearest prime that fits in 32 bits, but in fact this is the same thing since the primes around 2^32 are 4294967291 and 4294967311.

我试过，以确保不会有因整数溢出（因为我们与数字打交道一直到UINT_MAX）任何错误;我希望我没有犯了一个错误在那里。如果你想使用64位类型code可以简化（或者你知道你的号码是小于2 ^ 32-256），因为你就不必担心在循环条件环绕周围。另外这个想法更大的数字，只要你愿意来计算/存储小的素数达到所需的极限尺度。

I tried to make sure there wouldn't be any bugs due to integer overflow (since we're dealing with numbers right up to UINT_MAX); hopefully I didn't make a mistake there. The code could be simplified if you wanted to use 64-bit types (or you knew your numbers would be smaller than 2^32-256) since you wouldn't have to worry about wrapping around in the loop conditions. Also this idea scales for bigger numbers as long as you're willing to compute/store the small primes up to the needed limit.

我也应该注意到，小贷筛运行得相当快，这些数字（从粗略测量4-5毫秒），所以如果你是特别的内存匮乏，每次运行它​​，而不是存储小的素数是可行的（你可能会想在这种情况下，有效的标记[]数组更多的空间）

I should note also that the small-prime-sieve runs quite quickly for these numbers (4-5 ms from a rough measurement) so if you are especially memory-starved, running it every time instead of storing the small primes is doable (you'd probably want to make the mark[] arrays more space efficient in this case)

#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＆LT; = 2 ^ 16，你应该去高一点，如果黄金本身可能是大于2 ^ 32 - 1 ）。不一定是最快的方式，但是很简单，票友主要测试技术真正适合更大的范围。

---

You can sieve intervals in that range if you know primes up to 2^16 (there are only 6542 <= 2^16; you should go a bit higher if the prime itself could be greater than 2^32 - 1). Not necessarily the fastest way but very simple, and fancier prime testing techniques are really suited to much larger ranges.

基本上，做埃拉托色尼的定期筛获得小素数（说的第7000）。很明显，你只需要在程序的开始，一旦做到这一点，但它应该是非常快的。

Basically, do a regular Sieve of Eratosthenes to get the "small" primes (say the first 7000). Obviously you only need to do this once at the start of the program, but it should be very fast.

那么，假设你的目标号是A，考虑对n的一些价值区间[a-N / 2，+ N / 2）。也许N = 128是一个合理的地方开始;您可能需要尝试相邻的间隔，如果在第一个数字是全复合材料。

Then, supposing your "target" number is 'a', consider the interval [a-n/2, a+n/2) for some value of n. Probably n = 128 is a reasonable place to start; you may need to try adjacent intervals if the numbers in the first one are all composite.

对于每一个小的素数p，划掉它的倍数范围内，采用事业部找到从哪里开始。一种优化是，你只需要启动渡关倍数开始P * P（这意味着你可以停止审批一次素数P * p是区间以上）。

For every "small" prime p, cross out its multiples in the range, using division to find where to start. One optimization is that you only need to start crossing off multiples starting at p*p (which means that you can stop considering primes once p*p is above the interval).

大多数除了第几个素数将有间隔内任一或零的倍数;利用这一优势，你可以pre-忽略前几个质数的倍数。最简单的事情是忽略所有的偶数，但它并不少见忽视乘2，3，5;这留下全等1，7，11，13，17，19，23，29和30 MOD（有八个，筛分大范围时，它很好地映射到一个字节的位）。

Most of the primes except the first few will have either one or zero multiples inside the interval; to take advantage of this you can pre-ignore multiples of the first few primes. The simplest thing is to ignore all even numbers, but it's not uncommon to ignore multiples of 2, 3, and 5; this leaves integers congruent to 1, 7, 11, 13, 17, 19, 23, and 29 mod 30 (there are eight, which map nicely to the bits of a byte when sieving a large range).

...排序的去了一个切线那里;无论如何，一旦你处理所有的小素数（截止到P * P> A + N / 2）你只是看在你没有划掉号​​码区间;因为你想要的最接近开始寻找那里，并在两个方向向外搜索。

...Sort of went off on a tangent there; anyway once you've processed all the small primes (up till p*p > a+n/2) you just look in the interval for numbers you didn't cross out; since you want the closest to a start looking there and search outward in both directions.

这篇关于找到最近的素数在C无符号长整型（32位宽）的方法吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！