¿Una forma de encontrar el número primo más cercano a un entero largo sin signo (32 bits de ancho) en C?

Question

Estoy buscando una manera de encontrar el número primo más cercano. Mayor o menor que, no importa, simplemente el más cercano (sin desbordamiento, preferiblemente). En cuanto a la velocidad, si puede calcularla en aproximadamente 50 milisegundos en una máquina de 1 GHz (en software, ejecutándose dentro de Linux), tendría estar extático

Answer 1

ACTUALIZACIÓN 2: Reparado (de una manera dura) algunos errores que causaron respuestas incorrectas para n pequeño. ¡Gracias a Brett Hale por notarlo! También se agregaron algunos asertos para documentar algunas suposiciones.

ACTUALIZACIÓN: I codificado esto y parece lo suficientemente rápido para sus necesidades (1000 resuelto casos aleatorios a partir de [2^29, 2^32-1] en < 100 ms, en una máquina de 2,2 GHz - no una prueba rigurosa pero convincente, no obstante).

Está escrito en C++ ya que eso es lo que tenía mi código de criba (que he adaptado), pero la conversión a C debería ser sencilla. El uso de memoria también es (relativamente) pequeño, lo que puede ver por inspección.

Puede ver que debido a la forma en que se llama a la función, el número devuelto es el primo más cercano que cabe en 32 bits, pero de hecho es lo mismo ya que los números primos alrededor de 2^32 son 4294967291 y 4294967311.

Traté de asegurarme de que no hubiera ningún error debido al desbordamiento de enteros (ya que estamos tratando con números hasta UINT_MAX); con suerte no cometí un error allí. El código podría simplificarse si quisiera usar tipos de 64 bits (o si sabía que sus números serían más pequeños que 2^32-256), ya que no tendría que preocuparse por las condiciones del bucle. También esta idea se escala para números más grandes siempre que esté dispuesto a calcular/almacenar los primos pequeños hasta el límite necesario.

Debo notar también que el tamiz de cebado pequeño funciona bastante rápido para estos números (4-5 ms de una medición aproximada) así que si está especialmente hambriento de memoria, ejecútelo cada vez en lugar de almacenar los primos pequeños es factible (lo que probablemente quiere hacer la marca [] matrices más eficiente del espacio, en este caso)

#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'; 
    } 
    } 

---

puede tamiz intervalos en ese rango si sabe primos hasta 2^16 (allí son solo 6542 < = 2^16; debe aumentar un poco si el primo en sí podría ser mayor que 2^32 - 1). No necesariamente de la manera más rápida pero muy simple, y las técnicas de prueba primarias más sofisticadas son realmente adecuadas para gamas mucho más grandes.

Básicamente, haga un Tamiz regular de Eratóstenes para obtener los números primos "pequeños" (digamos los primeros 7000). Obviamente, solo necesita hacer esto una vez al inicio del programa, pero debe ser muy rápido.

Entonces, suponiendo que su número "objetivo" es 'a', considere el intervalo [a-n/2, a + n/2] para algún valor de n. Probablemente n = 128 es un lugar razonable para comenzar; es posible que deba probar los intervalos adyacentes si los números en el primero son todos compuestos.

Para cada "prime" p "pequeña", tache sus múltiplos en el rango, usando la división para buscar dónde comenzar. Una optimización es que solo necesita comenzar a tachar múltiplos comenzando en p * p (lo que significa que puede dejar de considerar primos una vez que p * p esté por encima del intervalo).

La mayoría de los números primos, excepto los primeros, tendrán uno o cero múltiplos dentro del intervalo; para aprovechar esto, puede ignorar los múltiplos de los primeros primos. Lo más simple es ignorar todos los números pares, pero no es raro ignorar los múltiplos de 2, 3 y 5; esto deja números enteros congruentes con 1, 7, 11, 13, 17, 19, 23 y 29 mod 30 (hay ocho, que se asocian muy bien con los bits de un byte cuando se tamiza un rango grande).

... Algo así como una tangente; de todos modos, una vez que haya procesado todos los números primos pequeños (hasta p * p> a + n/2) simplemente observe en el intervalo los números que no ha tachado; ya que quiere lo más cercano a un comienzo buscando allí y buscando hacia afuera en ambas direcciones.

Answer 2

El largest prime gap en el rango hasta (2^32 - 1) es (335). Hay (6542) números primos menores que (2^16) que pueden tabularse y usarse para tamizar valores impares sucesivos después de una configuración única. Obviamente, solo los números primos < = piso (sqrt (candidato)) deben probarse para un valor candidato particular.

Alternativamente: El deterministic variant of the Miller-Rabin test, con bases de SPRP: {2, 7, 61} es suficiente para probar la primalidad para un valor de 32 bits. Debido a la complejidad de la prueba (requiere exponenciación, etc.), dudo que sea tan rápido para candidatos tan pequeños.

Edit: En realidad, si multiplicar/reducir se puede mantener en 32 bits en exponenciación (podría necesitar soporte de 64 bits), la prueba M-R podría ser mejor. Los huecos primarios generalmente serán mucho más pequeños, lo que hace que la configuración del tamiz sea excesiva. Sin grandes tablas de búsqueda, etc., también puede recibir un impulso de una mejor localidad de caché.

Además: El producto de primos {2, 3, 5, 7, 11, 13, 17, 19, 23} = (223092870). Evalúe explícitamente a cualquier candidato en [2, 23]. Calcular el mayor divisor común: g = gcd(u, 223092870UL). Si es (g != 1), el candidato es compuesto. Si (g == 1 && u < (29 * 29)), el candidato (u > 23) es definitivamente primo. De lo contrario, pase a las pruebas más caras. Una sola prueba de gcd usando aritmética de 32 bits es muy barata, y según el teorema de Mertens (?), Esto detectará ~ 68.4% de todos números compuestos impares.