¿Tamiz segmentado de Eratóstenes?
Es bastante fácil hacer un colador simple:
for (int i=2; i<=N; i++){
if (sieve[i]==0){
cout << i << " is prime" << endl;
for (int j = i; j<=N; j+=i){
sieve[j]=1;
}
}
cout << i << " has " << sieve[i] << " distinct prime factors\n";
}
Pero ¿qué pasa cuando N es muy grande y no puedo mantener ese tipo de matriz en la memoria? He buscado enfoques de tamiz segmentado y parecen implicar encontrar números primos hasta sqrt(N), pero no entiendo cómo funciona. ¿Qué pasa si N es muy grande (digamos 10^18)?
Mi objetivo es adquirir el número de factores primos únicos por valor k para N grande, para cada k hasta N.
La idea básica de un tamiz segmentado es elegir los números primos de tamizado menores que la raíz cuadrada de n , elegir un tamaño de segmento razonablemente grande que, sin embargo, quepa en la memoria y luego tamizar cada uno de los segmentos por turno, comenzando por el más pequeño. En el primer segmento, se calcula el múltiplo más pequeño de cada factor de tamizado que se encuentra dentro del segmento, luego los múltiplos del factor de tamizado se marcan como compuestos de la manera normal; cuando se han utilizado todos los números primos de tamizado, los números restantes sin marcar en el segmento son primos. Luego, para el siguiente segmento, para cada tamizado principal ya conoce el primer múltiplo del segmento actual (fue el múltiplo que finalizó el tamizado para ese principal en el segmento anterior), por lo que tamiza en cada tamizado principal, y así sucesivamente. hasta que hayas terminado.
El tamaño de n no importa, excepto que un n mayor tardará más en tamizar que un n más pequeño ; el tamaño que importa es el tamaño del segmento, que debe ser tan grande como sea conveniente (por ejemplo, el tamaño de la memoria caché primaria de la máquina).
Puede ver una implementación simple de un tamiz segmentado aquí . Tenga en cuenta que un tamiz segmentado será mucho más rápido que el tamiz de cola prioritaria de O'Neill mencionado en otra respuesta; Si está interesado, hay una implementación aquí .
EDITAR: Escribí esto con un propósito diferente, pero lo mostraré aquí porque podría ser útil:
Aunque el Tamiz de Eratóstenes es muy rápido, requiere O(n) espacio. Eso se puede reducir a O(sqrt(n)) para los números primos de tamizado más O(1) para la matriz de bits realizando el tamizado en segmentos sucesivos. En el primer segmento, se calcula el múltiplo más pequeño de cada factor de tamizado que se encuentra dentro del segmento, luego los múltiplos del factor de tamizado se marcan como compuestos de la manera normal; cuando se han utilizado todos los números primos de tamizado, los números restantes sin marcar en el segmento son primos. Luego, para el siguiente segmento, el múltiplo más pequeño de cada tamizado principal es el múltiplo que finalizó el tamizado en el segmento anterior, y así el tamizado continúa hasta terminar.
Considere el ejemplo de tamiz de 100 a 200 en segmentos de 20. Los cinco números primos de tamizado son 3, 5, 7, 11 y 13. En el primer segmento de 100 a 120, la matriz de bits tiene diez ranuras, y la ranura 0 corresponde a 101. , la ranura k corresponde a 100+2k+1 y la ranura 9 corresponde a 119. El múltiplo más pequeño de 3 en el segmento es 105, correspondiente a la ranura 2; las ranuras 2+3=5 y 5+3=8 también son múltiplos de 3. El múltiplo más pequeño de 5 es 105 en la ranura 2, y la ranura 2+5=7 también es múltiplo de 5. El múltiplo más pequeño de 7 es 105 en la ranura 2, y la ranura 2+7=9 también es múltiplo de 7. Y así sucesivamente.
La función primesRange toma argumentos lo, hola y delta; lo y hi deben ser pares, con lo <hi, y lo debe ser mayor que sqrt(hi). El tamaño del segmento es dos veces delta. Ps es una lista enlazada que contiene los números primos menores que sqrt(hi), con 2 eliminado ya que se ignoran los números pares. Qs es una lista enlazada que contiene el múltiplo más pequeño en el segmento actual del tamiz principal correspondiente en la matriz de bits de tamiz. Después de cada segmento, lo avanza dos veces delta, por lo que el número correspondiente a un índice i de la matriz de bits del tamiz es lo + 2i + 1.
function primesRange(lo, hi, delta)
function qInit(p)
return (-1/2 * (lo + p + 1)) % p
function qReset(p, q)
return (q - delta) % p
sieve := makeArray(0..delta-1)
ps := tail(primes(sqrt(hi)))
qs := map(qInit, ps)
while lo < hi
for i from 0 to delta-1
sieve[i] := True
for p,q in ps,qs
for i from q to delta step p
sieve[i] := False
qs := map(qReset, ps, qs)
for i,t from 0,lo+1 to delta-1,hi step 1,2
if sieve[i]
output t
lo := lo + 2 * delta
Cuando se llama como rango de números primos (100, 200, 10), los números primos ps tamizados son [3, 5, 7, 11, 13]; qs es inicialmente [2, 2, 2, 10, 8] correspondiente a los múltiplos más pequeños 105, 105, 105, 121 y 117, y se restablece para el segundo segmento a [1, 2, 6, 0, 11] correspondiente al más pequeño múltiplos 123, 125, 133, 121 y 143.
Puedes ver este programa en acción enhttp://ideone.com/iHYr1f . Y además de los enlaces mostrados arriba, si estás interesado en programar con números primos, te recomiendo modestamente este ensayo en mi blog.
Es que vamos haciendo segmentados con el colador que tenemos. La idea básica es decir que tenemos que encontrar números primos entre 85 y 100. Tenemos que aplicar el tamiz tradicional, pero de la manera que se describe a continuación:
Entonces tomamos el primer número primo 2, dividimos el número inicial por 2 (85/2) y redondeamos a un número menor obtenemos p = 42, ahora multiplicamos nuevamente por 2 obtenemos p = 84, de aquí en adelante comenzamos a sumar 2 hasta el último número. Entonces, lo que hemos hecho es eliminar todos los factores de 2 (86,88,90,92,94,96,98,100) en el rango.
Tomamos el siguiente número primo 3, dividimos el número inicial por 3 (85/3) y redondeamos a un número menor obtenemos p = 28, ahora multiplicamos nuevamente por 3 obtenemos p = 84, de aquí en adelante comenzamos a sumar 3 hasta el último número. Entonces, lo que hemos hecho es eliminar todos los factores de 3 (87,90,93,96,99) en el rango.
Tome el siguiente número primo = 5 y así sucesivamente... Continúe con los pasos anteriores. Puede obtener los números primos (2,3,5,7, ...) utilizando el tamiz tradicional hasta sqrt(n). Y luego utilícelo para el tamiz segmentado.
Existe una versión de Sieve basada en colas de prioridad que produce tantos números primos como usted solicite, en lugar de todos hasta un límite superior. Se analiza en el artículo clásico "El tamiz genuino de Eratóstenes" y al buscar en Google "cola de prioridad del tamiz de Eratóstenes" se encuentran bastantes implementaciones en varios lenguajes de programación.
