Способ найти ближайшее простое число беззнакового длинного целого (32 бита в ширину) в C?

Я ищу способ найти самое близкое простое число. Большее или меньшее, это не имеет значения, просто самое близкое (без переполнения, желательно.) Что касается скорости, то если он может вычислить его примерно через 50 миллисекунд на машине с частотой 1 ГГц (в программном обеспечении, работающем внутри Linux), я бы быть в восторге.

Ответ 1

ОБНОВЛЕНИЕ 2. Исправлено (в тяжелом смысле) некоторые ошибки, вызвавшие неправильные ответы для небольших n. Спасибо Бретту Хейлу за то, что он заметил! Также добавлено несколько утверждений для документирования некоторых допущений.

ОБНОВЛЕНИЕ: я закодировал это и, кажется, достаточно быстро для ваших требований (решил 1000 случайных экземпляров из [2 ^ 29, 2 ^ 32-1] в < 100ms, на 2.2 GHz - не тщательный тест, но, тем не менее, убедительный).

Это написано на С++, так как я использовал мой ситовый код (который я адаптировал), но преобразование в 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 = lt; = 2 ^ 16; вы должны идти немного выше, если само начало может быть больше 2 ^ 32 - 1). Не обязательно самый быстрый способ, но очень простой, и более простые методы тестирования действительно подходят для гораздо больших диапазонов.

В основном, делайте регулярное сито Эратосфена, чтобы получить "маленькие" простые числа (скажем, первые 7000). Очевидно, вам нужно сделать это только один раз в начале программы, но это должно быть очень быстро.

Тогда, предположим, что ваш "целевой" номер "a", рассмотрим интервал [a-n/2, a + n/2) для некоторого значения n. Вероятно, n = 128 - это разумное место для начала; вам может понадобиться попробовать смежные интервалы, если числа в первом являются составными.

Для каждого "малого" простого p вычеркните его кратность в диапазоне, используя деление, чтобы найти, с чего начать. Одна оптимизация заключается в том, что вам нужно только начинать скрещивание кратных значений, начиная с p * p (это означает, что вы можете прекратить рассматривать простые числа, если p * p превышает интервал).

Большинство простых чисел, кроме первых, будут иметь один или нулевой кратный внутри интервала; Чтобы воспользоваться этим, вы можете предварительно игнорировать кратность первых нескольких простых чисел. Самое простое - игнорировать все четные числа, но нередко игнорировать кратные 2, 3 и 5; это оставляет целые числа, совпадающие с 1, 7, 11, 13, 17, 19, 23 и 29 мод 30 (их восемь, которые хорошо сопоставляются с битами байта при просеивании большого диапазона).

... Вид пошел по касательной; в любом случае, как только вы обработали все мелкие простые числа (вплоть до p * p > a + n/2), вы просто смотрите в интервале для чисел, которые вы не вычеркнули; так как вы хотите, чтобы ближайший к нему начал смотреть и искать в обоих направлениях.

Ответ 1

Ответ 2