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

Question

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

Answer 1

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

UPDATE: Я закодированы это и кажется достаточно быстр для ваших требований (решается 1000 случайных экземпляров из [2^29, 2^32-1] в < 100мс, на 2.2GHz машине - не строгое испытание, но тем не менее убедительное).

Это написано на C++, так как это мой ситовый код (который я адаптировал), но преобразование в 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 < = 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 mod 30 (их восемь, которые хорошо сопоставляются с битами байта при просеивании большого диапазона).

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

Answer 2

largest prime gap в диапазоне до (2^32 - 1) есть (335). Имеются (6542) простые числа меньше (2^16), которые могут быть сведены в таблицу и использованы для сита последовательных нечетных значений после одноразовой настройки. Очевидно, что только простые числа < = floor (sqrt (кандидат)) нуждаются в проверке на конкретное значение кандидата.

В качестве альтернативы:deterministic variant of the Miller-Rabin test с 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% от всех нечетных составных чисел.