algorithm - long - title tag
Dado el primer número N, ¿calcular el siguiente primer? (9)
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:
Distancia interprime frente al número primo
Solo para ver que es "aleatorio". Sin embargo ...
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?
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 primality 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 .
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).
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<double, std::milli> 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 compiladas 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 aumentar 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.
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.
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
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.
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.
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.