Dado el primer número N, ¿calcular el siguiente primer?

Un compañero de trabajo me acaba de decir que la colección de C # Dictionary cambia el tamaño por números primos por razones arcanas relacionadas con hash. Y mi pregunta inmediata fue, “¿cómo sabe cuál es el próximo momento álgido? ¿Cuentan una tabla gigante o computan sobre la marcha? Eso es un tiempo de ejecución no determinante y aterrador en un inserto que causa un cambio de tamaño”

Entonces mi pregunta es, dado N, que es un número primo, ¿cuál es la forma más eficiente de calcular el próximo número primo?

Se sabe que las brechas entre los números primos consecutivos son bastante pequeñas, con la primera brecha de más de 100 ocurriendo para el número primo 370261. Eso significa que incluso una simple fuerza bruta será lo suficientemente rápida en la mayoría de las circunstancias, tomando O (ln (p) * sqrt (p)) en promedio.

Para p = 10,000 eso es O (921) operaciones. Teniendo en cuenta que realizaremos esto una vez cada inserción O (ln (p)) (en términos generales), esto está dentro de las limitaciones de la mayoría de los problemas que toman el orden de un milisegundo en la mayoría del hardware moderno.

Hace aproximadamente un año estaba trabajando en esta área para libc ++ mientras implementaba los contenedores desordenados (hash) para C ++ 11. Pensé que iba a compartir mis experiencias aquí. Esta experiencia apoya la respuesta aceptada de marcog para una definición razonable de “fuerza bruta”.

Eso significa que incluso una simple fuerza bruta será lo suficientemente rápida en la mayoría de las circunstancias, tomando O (ln (p) * sqrt (p)) en promedio.

Desarrollé varias implementaciones de size_t next_prime(size_t n) donde la especificación para esta función es:

Devuelve: el primo más pequeño que es mayor que o igual a n .

Cada implementación de next_prime va acompañada de una función auxiliar is_prime . is_prime debe considerarse un detalle de implementación privada; no destinado a ser llamado directamente por el cliente. Por supuesto, cada una de estas implementaciones fue probada para ser correcta, pero también probada con la siguiente prueba de rendimiento:

 int main() { typedef std::chrono::high_resolution_clock Clock; typedef std::chrono::duration ms; Clock::time_point t0 = Clock::now(); std::size_t n = 100000000; std::size_t e = 100000; for (std::size_t i = 0; i < e; ++i) n = next_prime(n+1); Clock::time_point t1 = Clock::now(); std::cout << e/ms(t1-t0).count() << " primes/millisecond\n"; return n; } 

Debo enfatizar que esta es una prueba de rendimiento, y no refleja el uso típico, que se parecería más a:

 // Overflow checking not shown for clarity purposes n = next_prime(2*n + 1); 

Todas las pruebas de rendimiento fueron comstackdas con:

 clang++ -stdlib=libc++ -O3 main.cpp 

Implementación 1

Hay siete implementaciones. El propósito de mostrar la primera implementación es demostrar que si no deja de probar la cepa x candidata para los factores en sqrt(x) entonces no ha logrado ni siquiera lograr una implementación que podría clasificarse como fuerza bruta. Esta implementación es brutalmente lenta .

 bool is_prime(std::size_t x) { if (x < 2) return false; for (std::size_t i = 2; i < x; ++i) { if (x % i == 0) return false; } return true; } std::size_t next_prime(std::size_t x) { for (; !is_prime(x); ++x) ; return x; } 

Para esta implementación, solo tuve que establecer e en 100 en lugar de 100000, solo para obtener un tiempo de ejecución razonable:

 0.0015282 primes/millisecond 

Implementación 2

Esta implementación es la más lenta de las implementaciones de fuerza bruta y la única diferencia con respecto a la implementación 1 es que deja de probar la excelencia cuando el factor supera el sqrt(x) .

 bool is_prime(std::size_t x) { if (x < 2) return false; for (std::size_t i = 2; true; ++i) { std::size_t q = x / i; if (q < i) return true; if (x % i == 0) return false; } return true; } std::size_t next_prime(std::size_t x) { for (; !is_prime(x); ++x) ; return x; } 

Tenga en cuenta que sqrt(x) no se calcula directamente, sino que se deduce mediante q < i . Esto acelera las cosas por un factor de miles:

 5.98576 primes/millisecond 

y valida la predicción de marcog:

... esto está dentro de las limitaciones de la mayoría de los problemas que toman el orden de un milisegundo en la mayoría de los equipos modernos.

Implementación 3

Casi se puede duplicar la velocidad (al menos en el hardware que estoy usando) al evitar el uso del operador % :

 bool is_prime(std::size_t x) { if (x < 2) return false; for (std::size_t i = 2; true; ++i) { std::size_t q = x / i; if (q < i) return true; if (x == q * i) return false; } return true; } std::size_t next_prime(std::size_t x) { for (; !is_prime(x); ++x) ; return x; } 11.0512 primes/millisecond 

Implementación 4

Hasta ahora, ni siquiera he usado el conocimiento común de que 2 es el único primo par. Esta implementación incorpora ese conocimiento, casi duplicando la velocidad nuevamente:

 bool is_prime(std::size_t x) { for (std::size_t i = 3; true; i += 2) { std::size_t q = x / i; if (q < i) return true; if (x == q * i) return false; } return true; } std::size_t next_prime(std::size_t x) { if (x <= 2) return 2; if (!(x & 1)) ++x; for (; !is_prime(x); x += 2) ; return x; } 21.9846 primes/millisecond 

La implementación 4 es probablemente lo que la mayoría de la gente tiene en mente cuando piensa en la "fuerza bruta".

Implementación 5

Usando la siguiente fórmula, puede elegir fácilmente todos los números que son divisibles ni por 2 ni por 3:

 6 * k + {1, 5} 

donde k> = 1. La siguiente implementación usa esta fórmula, pero implementada con un bonito truco xor:

 bool is_prime(std::size_t x) { std::size_t o = 4; for (std::size_t i = 5; true; i += o) { std::size_t q = x / i; if (q < i) return true; if (x == q * i) return false; o ^= 6; } return true; } std::size_t next_prime(std::size_t x) { switch (x) { case 0: case 1: case 2: return 2; case 3: return 3; case 4: case 5: return 5; } std::size_t k = x / 6; std::size_t i = x - 6 * k; std::size_t o = i < 2 ? 1 : 5; x = 6 * k + o; for (i = (3 + o) / 2; !is_prime(x); x += i) i ^= 6; return x; } 

Esto significa que el algoritmo tiene que verificar solo 1/3 de los enteros para la excelencia en lugar de 1/2 de los números y la prueba de rendimiento muestra la velocidad esperada de casi el 50%:

 32.6167 primes/millisecond 

Implementación 6

Esta implementación es una extensión lógica de la implementación 5: utiliza la siguiente fórmula para calcular todos los números que no son divisibles por 2, 3 y 5:

 30 * k + {1, 7, 11, 13, 17, 19, 23, 29} 

También desenrolla el bucle interno dentro de is_prime, y crea una lista de "primos pequeños" que es útil para tratar con números menores a 30.

 static const std::size_t small_primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; static const std::size_t indices[] = { 1, 7, 11, 13, 17, 19, 23, 29 }; bool is_prime(std::size_t x) { const size_t N = sizeof(small_primes) / sizeof(small_primes[0]); for (std::size_t i = 3; i < N; ++i) { const std::size_t p = small_primes[i]; const std::size_t q = x / p; if (q < p) return true; if (x == q * p) return false; } for (std::size_t i = 31; true;) { std::size_t q = x / i; if (q < i) return true; if (x == q * i) return false; i += 6; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 4; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 2; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 4; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 2; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 4; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 6; q = x / i; if (q < i) return true; if (x == q * i) return false; i += 2; } return true; } std::size_t next_prime(std::size_t n) { const size_t L = 30; const size_t N = sizeof(small_primes) / sizeof(small_primes[0]); // If n is small enough, search in small_primes if (n <= small_primes[N-1]) return *std::lower_bound(small_primes, small_primes + N, n); // Else n > largest small_primes // Start searching list of potential primes: L * k0 + indices[in] const size_t M = sizeof(indices) / sizeof(indices[0]); // Select first potential prime >= n // Known a-priori n >= L size_t k0 = n / L; size_t in = std::lower_bound(indices, indices + M, n - k0 * L) - indices; n = L * k0 + indices[in]; while (!is_prime(n)) { if (++in == M) { ++k0; in = 0; } n = L * k0 + indices[in]; } return n; } 

Esto podría decirse que va más allá de la "fuerza bruta" y es bueno para boost la velocidad otro 27.5% para:

 41.6026 primes/millisecond 

Implementación 7

Es práctico jugar el juego anterior para una iteración más, desarrollando una fórmula para números no divisibles por 2, 3, 5 y 7:

 210 * k + {1, 11, ...}, 

El código fuente no se muestra aquí, pero es muy similar a la implementación 6. Esta es la implementación que elegí usar realmente para los contenedores no ordenados de libc ++ , y ese código fuente es de código abierto (se encuentra en el enlace).

Esta iteración final es buena para otro impulso de velocidad del 14.6% para:

 47.685 primes/millisecond 

El uso de este algoritmo asegura que los clientes de las tablas hash de libc ++ puedan elegir cualquier primo que decidan que sea más beneficioso para su situación, y el rendimiento para esta aplicación es bastante aceptable.

En caso de que alguien tenga curiosidad:

Usando el reflector, determiné que .Net usa una clase estática que contiene una lista codificada de ~ 72 primos que van hasta 7199369 que escanea para el primo más pequeño que es al menos dos veces el tamaño actual, y para tamaños mayores que eso calcula el Próxima generación por división de prueba de todos los números impares hasta el cuadrado del número potencial. Esta clase es inmutable y segura para subprocesos (es decir, primos más grandes no se almacenan para uso futuro).

Un buen truco es usar un tamiz parcial. Por ejemplo, ¿cuál es el siguiente primo que sigue al número N = 2534536543556?

Compruebe el módulo de N con respecto a una lista de primos pequeños. Así…

 mod(2534536543556,[3 5 7 11 13 17 19 23 29 31 37]) ans = 2 1 3 6 4 1 3 4 22 16 25 

Sabemos que el siguiente primo siguiente N debe ser un número impar, y podemos descartar inmediatamente todos los múltiplos impares de esta lista de primos pequeños. Estos módulos nos permiten tamizar múltiplos de esos primos pequeños. Si usáramos los primos pequeños hasta 200, podemos usar este esquema para descartar inmediatamente la mayoría de los números primos potenciales mayores que N, excepto por una lista pequeña.

Más explícitamente, si estamos buscando un número primo más allá de 2534536543556, no puede ser divisible por 2, por lo que debemos considerar solo los números impares más allá de ese valor. Los módulos anteriores muestran que 2534536543556 es congruente con 2 mod 3, por lo tanto, 2534536543556 + 1 es congruente con 0 mod 3, como debe ser 2534536543556 + 7, 2534536543556 + 13, etc. Efectivamente, podemos separar muchos de los números sin necesidad para probarlos en primalidad y sin ninguna división de prueba.

Del mismo modo, el hecho de que

 mod(2534536543556,7) = 3 

nos dice que 2534536543556 + 4 es congruente con 0 mod 7. Por supuesto, ese número es par, por lo que podemos ignorarlo. Pero 2534536543556 + 11 es un número impar que es divisible por 7, como 2534536543556 + 25, etc. Nuevamente, podemos excluir estos números como claramente compuestos (porque son divisibles por 7) y por lo tanto no primos.

Utilizando solo la pequeña lista de números primos hasta 37, podemos excluir la mayoría de los números que siguen inmediatamente a nuestro punto de partida de 2534536543556, con la excepción de algunos:

 {2534536543573 , 2534536543579 , 2534536543597} 

De esos números, ¿son primos?

 2534536543573 = 1430239 * 1772107 2534536543579 = 99833 * 25387763 

Hice el esfuerzo de proporcionar las factorizaciones principales de los primeros dos números en la lista. Ver que son compuestos, pero los factores primos son grandes. Por supuesto, esto tiene sentido, ya que ya nos hemos asegurado de que ningún número que quede pueda tener factores primarios pequeños. El tercero en nuestra lista corta (2534536543597) es de hecho el primer número primo más allá de N. El esquema de cribado que he descrito tenderá a dar como resultado números que son primos, o están compuestos de factores primos generalmente grandes. Entonces necesitábamos aplicar una prueba explícita de primalidad a solo unos pocos números antes de encontrar el próximo primo.

Un esquema similar produce rápidamente el siguiente primo superior a N = 1000000000000000000000000000, como 1000000000000000000000000103.

Solo unos pocos experimentos con distancia entre primos.


Este es un complemento para visualizar otras respuestas.

Obtuve los números primos desde el 100.000 (= 1,299,709) hasta el 200,000 (= 2,750,159)

Algunos datos:

 Maximum interprime distance = 148 Mean interprime distance = 15 

Gráfico de frecuencia de distancia interprime:

texto alternativo

Distancia interprime frente al número primo

texto alternativo

Solo para ver que es “aleatorio”. Sin embargo …

No hay función f (n) para calcular el próximo número primo. En cambio, se debe probar la primalidad de un número.

También es muy útil, al encontrar el enésimo número primo, conocer todos los números primos desde el 1er hasta (n-1) th, porque esos son los únicos números que deben probarse como factores.

Como resultado de estas razones, no me sorprendería que haya un conjunto precalculado de números primos grandes. Realmente no tiene sentido para mí si ciertos números primos necesitan ser recalculados repetidamente.

Como otros ya han notado, todavía no se ha encontrado un medio para encontrar el próximo número primo dado el primo actual. Por lo tanto, la mayoría de los algoritmos se centran más en utilizar un medio rápido para verificar la primalidad, ya que debe verificar n / 2 de los números entre su primo conocido y el siguiente.

Dependiendo de la aplicación, también puede salirse con la tarea de codificar una tabla de búsqueda, como lo señala Paul Wheeler .

Por pura novedad, siempre hay este enfoque:

 #!/usr/bin/perl for $p ( 2 .. 200 ) { next if (1x$p) =~ /^(11+)\1+$/; for ($n=1x(1+$p); $n =~ /^(11+)\1+$/; $n.=1) { } printf "next prime after %d is %d\n", $p, length($n); } 

que por supuesto produce

 next prime after 2 is 3 next prime after 3 is 5 next prime after 5 is 7 next prime after 7 is 11 next prime after 11 is 13 next prime after 13 is 17 next prime after 17 is 19 next prime after 19 is 23 next prime after 23 is 29 next prime after 29 is 31 next prime after 31 is 37 next prime after 37 is 41 next prime after 41 is 43 next prime after 43 is 47 next prime after 47 is 53 next prime after 53 is 59 next prime after 59 is 61 next prime after 61 is 67 next prime after 67 is 71 next prime after 71 is 73 next prime after 73 is 79 next prime after 79 is 83 next prime after 83 is 89 next prime after 89 is 97 next prime after 97 is 101 next prime after 101 is 103 next prime after 103 is 107 next prime after 107 is 109 next prime after 109 is 113 next prime after 113 is 127 next prime after 127 is 131 next prime after 131 is 137 next prime after 137 is 139 next prime after 139 is 149 next prime after 149 is 151 next prime after 151 is 157 next prime after 157 is 163 next prime after 163 is 167 next prime after 167 is 173 next prime after 173 is 179 next prime after 179 is 181 next prime after 181 is 191 next prime after 191 is 193 next prime after 193 is 197 next prime after 197 is 199 next prime after 199 is 211 

Dejando a un lado toda la diversión y los juegos, es bien sabido que el tamaño óptimo de la tabla hash es rigurosamente demostrable como número primo de la forma 4N−1 . Entonces, solo encontrar el próximo primo es insuficiente. Tienes que hacer el otro control, también.

Por lo que recuerdo, utiliza el número primo al lado del doble del tamaño actual. No calcula ese número primo – hay una tabla con números precargados de hasta un gran valor (no exactamente, alrededor de 10 000 000). Cuando se alcanza ese número, utiliza algún algoritmo ingenuo para obtener el siguiente número (como curNum = curNum + 1) y lo valida utilizando algunos de estos métodos: http://en.wikipedia.org/wiki/Prime_number#Verifying_primality