Начин да се намери най-близкото просто число до дълго цяло число без знак (широко 32 бита) в C?

АКТУАЛИЗАЦИЯ 2: Коригирани (по тежък начин) някои грешки, които причиняваха грешни отговори за малки n. Благодаря на Брет Хейл, че забеляза! Също така са добавени някои твърдения за документиране на някои предположения.

АКТУАЛИЗАЦИЯ: Кодирах това и изглежда достатъчно бързо за вашите изисквания (решени 1000 произволни екземпляра от [2^29, 2^32-1] за ‹100ms, на 2,2GHz машина -- не е строг тест, но въпреки това е убедителен).

Написано е на C++, тъй като това беше моят код на sieve (от който адаптирах), но преобразуването в C трябва да е лесно. Използването на памет също е (сравнително) малко, което можете да видите чрез проверка.

Можете да видите, че поради начина, по който се извиква функцията, върнатото число е най-близкото просто число, което се побира в 32 бита, но всъщност това е едно и също нещо, тъй като простите числа около 2^32 са 4294967291 и 4294967311.

Опитах се да се уверя, че няма да има грешки поради целочислено препълване (тъй като имаме работа с числа точно до UINT_MAX); дано не съм сгрешил там. Кодът може да бъде опростен, ако искате да използвате 64-битови типове (или сте знаели, че вашите числа ще бъдат по-малки от 2^32-256), тъй като няма да се налага да се притеснявате от обвиване в условията на цикъла. Също така тази идея се мащабира за по-големи числа, стига да сте готови да изчислите/съхраните малките прости числа до необходимия лимит.

Трябва да отбележа също, че ситото за малки прости числа работи доста бързо за тези числа (4-5 ms от грубо измерване), така че ако имате особено недостиг на памет, стартирането му всеки път, вместо да съхранявате малките прости числа, е възможно (вие вероятно бих искал да направя масивите 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^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), просто поглеждате в интервала за числа, които не сте задраскали; тъй като искате най-близо до началото да гледате там и да търсите навън и в двете посоки.

Най-големият прост пропуск в диапазона до (2^32 - 1) е (335 ). Има (6542) прости числа, по-малки от (2^16), които могат да бъдат таблични и използвани за пресяване на последователни нечетни стойности след еднократна настройка. Очевидно е, че само простите числа ‹= floor(sqrt(candidate)) трябва да бъдат тествани за конкретна кандидатска стойност.

Алтернативно: детерминистичният вариант на 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) определено е първичен. В противен случай преминете към по-скъпите тестове. Единичен gcd тест, използващ 32-битова аритметика, е много евтин и според теоремата на Мертенс (?) това ще открие ~ 68,4% от всички нечетни съставни числа.