algorithm - factor - sieve eratosthenes implementation

Tamiz segmentado de Eratóstenes

Question

Es bastante fácil hacer un simple colador:

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 criba segmentada y parecen implicar encontrar primos hasta sqrt (N), pero no entiendo cómo funciona. ¿Qué pasa si N es muy grande (digamos 10 ^ 18)?

Answer 1

Basado en la respuesta de Swapnil Kumar, hice el siguiente algoritmo en C. Fue construido con mingw32-make.exe.

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
int main()
{
const int MAX_PRIME_NUMBERS = 5000000;//The number of prime numbers we are looking for
long long *prime_numbers = malloc(sizeof(long long) * MAX_PRIME_NUMBERS);
prime_numbers[0] = 2;
prime_numbers[1] = 3;
prime_numbers[2] = 5;
prime_numbers[3] = 7;
prime_numbers[4] = 11;
prime_numbers[5] = 13;
prime_numbers[6] = 17;
prime_numbers[7] = 19;
prime_numbers[8] = 23;
prime_numbers[9] = 29;
const int BUFFER_POSSIBLE_PRIMES = 29 * 29;//Because the greatest prime number we have is 29 in the 10th position so I started with a block of 841 numbers
int qt_calculated_primes = 10;//10 because we initialized the array with the ten first primes
int possible_primes[BUFFER_POSSIBLE_PRIMES];//Will store the booleans to check valid primes
long long iteration = 0;//Used as multiplier to the range of the buffer possible_primes
int i;//Simple counter for loops
while(qt_calculated_primes < MAX_PRIME_NUMBERS)
{
for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++)
possible_primes[i] = 1;//set the number as prime
int biggest_possible_prime = sqrt((iteration + 1) * BUFFER_POSSIBLE_PRIMES);
int k = 0;
long long prime = prime_numbers[k];//First prime to be used in the check
while (prime <= biggest_possible_prime)//We don''t need to check primes bigger than the square root
{
for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++)
if ((iteration * BUFFER_POSSIBLE_PRIMES + i) % prime == 0)
possible_primes[i] = 0;
if (++k == qt_calculated_primes)
break;
prime = prime_numbers[k];
}
for (i = 0; i < BUFFER_POSSIBLE_PRIMES; i++)
if (possible_primes[i])
{
if ((qt_calculated_primes < MAX_PRIME_NUMBERS) && ((iteration * BUFFER_POSSIBLE_PRIMES + i) != 1))
{
prime_numbers[qt_calculated_primes] = iteration * BUFFER_POSSIBLE_PRIMES + i;
printf("%d/n", prime_numbers[qt_calculated_primes]);
qt_calculated_primes++;
} else if (!(qt_calculated_primes < MAX_PRIME_NUMBERS))
break;
}
iteration++;
}
return 0;
}

Establece un máximo de números primos que se encuentran, luego se inicializa una matriz con números primos conocidos como 2, 3, 5 ... 29. Así que hacemos un buffer que almacenará los segmentos de posibles primos, este buffer no puede ser mayor que el poder del primo inicial más grande que en este caso es 29.

Estoy seguro de que hay muchas optimizaciones que se pueden hacer para mejorar el rendimiento, como paralelizar el proceso de análisis de segmentos y omitir números que son múltiples de 2, 3 y 5, pero sirve como ejemplo de bajo consumo de memoria.

Answer 2

Es solo que estamos segmentando con el tamiz que tenemos. La idea básica es, digamos, que tenemos que encontrar números primos entre 85 y 100. Tenemos que aplicar el tamiz tradicional, pero en la forma que se describe a continuación:

Así que tomamos el primer número primo 2, dividimos el número inicial por 2 (85/2) y redondeando a un número más pequeño obtenemos p = 42, ahora multiplicamos nuevamente por 2 obtenemos p = 84, a partir de aquí comenzamos a sumar 2 hasta el último número. Así que lo que hemos hecho es que hemos eliminado todos los factores de 2 (86,88,90,92,94,96,98,100) en el rango.

Tomamos el próximo número primo 3, dividimos el número inicial por 3 (85/3) y redondeamos a un número más pequeño obtenemos p = 28, ahora multiplicamos nuevamente por 3 obtenemos p = 84, de aquí en adelante comenzamos a agregar 3 hasta el último número. Así que lo que hemos hecho es que hemos eliminado todos los factores de 3 (87,90,93,96,99) en el rango.

Tome el siguiente número primo = 5 y así sucesivamente .................. Siga haciendo los pasos anteriores. Puede obtener los números primos (2,3,5,7, ...) usando el tamiz tradicional hasta sqrt (n) .Y luego úselo para el tamiz segmentado.

Answer 3

Hay una versión de Sieve basada en colas de prioridad que produce tantos números primos como usted solicite, en lugar de todos ellos hasta un límite superior. Se discute en el clásico "The Genuine Sieve of Eratosthenes" y en Google para "tamize of eratosthenes priority queue" aparecen bastantes implementaciones en varios lenguajes de programación.

Answer 4

La idea básica de un tamiz segmentado es elegir los primos de cribado menores que la raíz cuadrada de n , elegir un tamaño de segmento razonablemente grande que, sin embargo, encaje en la memoria, y luego tamizar cada uno de los segmentos, empezando por el más pequeño. En el primer segmento, se calcula el múltiplo más pequeño de cada primo de cribado que se encuentra dentro del segmento, luego los múltiplos del primo de tamizado se marcan como compuestos de la manera normal; cuando se han utilizado todos los primos de cribado, los números restantes no marcados en el segmento son primos. Luego, para el siguiente segmento, para cada primo de cribado ya conoce el primer múltiplo en el segmento actual (fue el múltiplo que finalizó el tamizado para ese primo en el segmento anterior), por lo que tamiza en cada primo de tamizado, y así sucesivamente hasta que hayas terminado.

El tamaño de n no importa, excepto que una n más grande tardará más en cerrarse que una n más pequeña; 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é principal en la máquina).

Puede ver una implementación simple de un tamiz segmentado here . Tenga en cuenta que un tamiz segmentado será mucho más rápido que el tamiz de cola de prioridad de O''Neill mencionado en otra respuesta; si estás interesado, hay una implementación here .

EDITAR: Escribí esto para 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 primos de cribado más O (1) para el bitarray realizando el cribado en segmentos sucesivos. En el primer segmento, se calcula el múltiplo más pequeño de cada prima de tamizado que está dentro del segmento, luego los múltiplos del primo de tamizado se marcan compuestos de la manera normal; cuando se han utilizado todos los primos de cribado, los números restantes no marcados en el segmento son primos. Luego, para el siguiente segmento, el múltiplo más pequeño de cada primo de tamizado es el múltiple que terminó el tamizado en el segmento anterior, por lo que el tamizado continúa hasta el final.

Considere el ejemplo del tamiz de 100 a 200 en segmentos de 20. Los cinco primos de tamizado son 3, 5, 7, 11 y 13. En el primer segmento de 100 a 120, el bitarray tiene diez ranuras, con el slot 0 correspondiente 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 máquinas tragamonedas 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 un 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 un múltiplo de 7. Y así sucesivamente.

Function primesRange toma argumentos lo, hi y delta; lo y ho 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 vinculada que contiene los primos de cribado menores que sqrt (hi), con 2 eliminados ya que se ignoran los números pares. Qs es una lista vinculada que contiene el más abierto en el bitarray del tamiz del múltiplo más pequeño en el segmento actual del primo de tamizado correspondiente. Después de cada segmento, lo avanza dos veces delta, por lo que el número correspondiente a un índice i del tamiz bitarray 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 primesRange (100, 200, 10), las primes de cribado ps son [3, 5, 7, 11, 13]; qs es inicialmente [2, 2, 2, 10, 8] correspondiente a los múltiplos 105, 105, 105, 121 y 117 más pequeños, y se restablece para el segundo segmento a [1, 2, 6, 0, 11] correspondiente a los más pequeños múltiplos 123, 125, 133, 121 y 143.

Puede ver este programa en acción en . Y además de los enlaces que se muestran arriba, si está interesado en programar con números primos, recomiendo modestamente este ensayo en mi blog.

Answer 5

Si alguien quisiera ver la implementación de C ++, aquí está el mío:

void sito_delta( int delta, std::vector<int> &res)
{
std::unique_ptr<int[]> results(new int[delta+1]);
for(int i = 0; i <= delta; ++i)
results[i] = 1;
int pierw = sqrt(delta);
for (int j = 2; j <= pierw; ++j)
{
if(results[j])
{
for (int k = 2*j; k <= delta; k+=j)
{
results[k]=0;
}
}
}
for (int m = 2; m <= delta; ++m)
if (results[m])
{
res.push_back(m);
std::cout<<","<<m;
}
};
void sito_segment(int n,std::vector<int> &fiPri)
{
int delta = sqrt(n);
if (delta>10)
{
sito_segment(delta,fiPri);
// COmpute using fiPri as primes
// n=n,prime = fiPri;
std::vector<int> prime=fiPri;
int offset = delta;
int low = offset;
int high = offset * 2;
while (low < n)
{
if (high >=n ) high = n;
int mark[offset+1];
for (int s=0;s<=offset;++s)
mark[s]=1;
for(int j = 0; j< prime.size(); ++j)
{
int lowMinimum = (low/prime[j]) * prime[j];
if(lowMinimum < low)
lowMinimum += prime[j];
for(int k = lowMinimum; k<=high;k+=prime[j])
mark[k-low]=0;
}
for(int i = low; i <= high; i++)
if(mark[i-low])
{
fiPri.push_back(i);
std::cout<<","<<i;
}
low=low+offset;
high=high+offset;
}
}
else
{
std::vector<int> prime;
sito_delta(delta, prime);
//
fiPri = prime;
//
int offset = delta;
int low = offset;
int high = offset * 2;
// Process segments one by one
while (low < n)
{
if (high >= n) high = n;
int mark[offset+1];
for (int s = 0; s <= offset; ++s)
mark[s] = 1;
for (int j = 0; j < prime.size(); ++j)
{
// find the minimum number in [low..high] that is
// multiple of prime[i] (divisible by prime[j])
int lowMinimum = (low/prime[j]) * prime[j];
if(lowMinimum < low)
lowMinimum += prime[j];
//Mark multiples of prime[i] in [low..high]
for (int k = lowMinimum; k <= high; k+=prime[j])
mark[k-low] = 0;
}
for (int i = low; i <= high; i++)
if(mark[i-low])
{
fiPri.push_back(i);
std::cout<<","<<i;
}
low = low + offset;
high = high + offset;
}
}
};
int main()
{
std::vector<int> fiPri;
sito_segment(1013,fiPri);
}