ОБНОВЛЕНИЕ 2 : Исправлены (неуклюже) некоторые ошибки, которые вызывали неправильные ответы для маленьких n. Спасибо Бретту Хейлу за внимание! Также добавлены некоторые утверждения, чтобы документировать некоторые предположения.
ОБНОВЛЕНИЕ : я закодировал это, и оно кажется достаточно быстрым для ваших требований (решено 1000 случайных случаев из [2 ^ 29, 2 ^ 32-1] за <100 мс, на машине с частотой 2,2 ГГц) - не строгий тест, но, тем не менее, убедительный). </p>
Он написан на 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 ^ 16; вам следует пойти немного выше, если простое число может быть больше 2 ^ 32 - 1) , Не обязательно самый быстрый способ, но очень простой и причудливый метод первичного тестирования действительно подходит для гораздо больших диапазонов. </p>
Обычно делайте обычное сито Эратосфена, чтобы получить «маленькие» простые числа (скажем, первые 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), вы просто смотрите в интервале числа, которые вы не вычеркнули; так как вы хотите, чтобы самый близкий к началу смотрел туда и искал наружу в обоих направлениях.