(void *) blog

Posted on by fortytwo_de


The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

La solución más sencilla es calcular los números primos en el intervalo (1, n] y sumarlos. Que efectivamente es la for ma de resolver este problema, pero el problema viene a la hora de calcular primos, especialmente cuando el n es un número relativamente alto (2.000.000).

Cómo no calcular números primos rápidamente

En otros problemas he utilizado la función isprime con la optimización de i = sqrt(n):

bool isprime(int target) { 
    if(target == 1) return false;

    for(size_t i = 2; i*i <= target; i++)
            if(target % i == 0)
                    return false;

    return true;
}             

Y simplemente iterar entre 1 y n, comprobando si cada número es primo, y si lo es, sumarlo.

int main(int argc, char** argv) {       
    if(argc != 2) return -1;
    unsigned long int target = atoi(argv[1]), sum = 0;

    for(size_t i = 2; i < target; i++) {
        if(isprime(i)) 
            sum += i;
    }

    cout << sum << endl;
}

El problema es que esta solución es muy ineficaz a la hora de calcular los primos de números grandes, y aunque es verdad que este programa resolvería el problema (dado suficiente tiempo), no es la solución elegante que se busca para este problema.

La criba de Eratóstenes

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N.

(Wikipedia)

Es el típico ejercicio que se hace en sexto de primaria, marcando los números que son múltiplos hasta que se llega al final, cuando solo quedan los números primos en un intervalo.

Desde luego es mucho más óptimo que la función isprime, ya que tiene complejidad O(n log^2 n log log n).

Mi implementación de la criba en C++ es la siguiente:

vector<int> eratosthenes_sieve(int start, int end) {
    vector<bool> eratosthenes_matrix(end - start + 1, true);

    for(size_t i = start; i*i <= end; i++) {
        if(i == 1) continue;
        if(!eratosthenes_matrix[i]) continue;

        for(size_t ii = 2; ii <= ((end - start + 1) / i); ii++) {
            eratosthenes_matrix[ii*i] = false;
        }
    }

    vector<int> result;
    for(size_t i = 0; i < eratosthenes_matrix.size(); i++) {
        if(i < 2) continue;
        if(eratosthenes_matrix[i]) 
            result.push_back(i);
    }

    return result;
}

Aquí hay varias cosas que entender, voy a ir comentando el código por bloques:

vector<bool> eratosthenes_matrix(end - start + 1, true);

Constructor del vector en el que voy a "marcar" los números que son múltiplos. Aquí aprovecho el constructor explicit vector (size_type n, const T& value); para asegurarme de que todos los números tienen como valor inicial true.

for(size_t i = start; i*i <= end; i++)

Esta es la optimización estándar para estos problemas: i = sqrt(n).

if(i == 1) continue;
if(!eratosthenes_matrix[i]) continue;

Si el número es 1 o ya está marcado (marcado como false, es decir, no es primo), se sale del bucle, ya que todos sus múltiplos ya se han marcado.

for(size_t ii = 2; ii <= ((end - start + 1) / i); ii++)

En este bucle se cogen todos los múltiplos de un número para marcarlos. ii llega como máximo a (tamaño del vector)/i, ya que nunca va a haber un múltiplo por encima de ese número.

eratosthenes_matrix[ii*i] = false;

El múltiplo ii*i se marca, ya que no es primo.

vector<int> result;
for(size_t i = 0; i < eratosthenes_matrix.size(); i++) {
    if(i < 2) continue;
    if(eratosthenes_matrix[i]) 
        result.push_back(i);
}

return result;

El resultado de la función es un vector de números enteros, así que este bucle busca los números que no están marcados en erastothenes_matrix y los mete en el nuevo vector.

Finalmente, ya teniendo una función que calcula los factores primos de un número, se pueden sumar fácilmente.

int main(int argc, char** argv) {
    if(argc != 2) return -1;
    int target = atoi(argv[1]);

    vector<int> v_primes = eratosthenes_sieve(1, target);
    unsigned long int sum = 0;
    for(size_t i = 0; i < v_primes.size(); i++)
        sum += v_primes[i];

    cout << sum << endl;
}

Posted on by fortytwo_de | Posted in Algoritmos, C, Matemáticas, Programación, Project Euler


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>