(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.

Continue reading

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


Posted on by fortytwo_de


El post de hoy va a ser más denso que los demás. Avisados estáis.

El programa más simple

… más que Hello World

int main() {
    return 0;
}

Probablemente sea el programa más simple que se puede escribir en C sin que salten errores de compilación. Pero en realidad, este programa ya hace muchas cosas.

Para entender mejor lo que hace, lo voy a destripar con -S en gcc.

$ gcc simple.c -S

Y el resultado es bastante largo, pero voy a omitir las partes que pertenencen a la gestión del stack frame y todas estas cosas que los sistemas operativos modernos tienen.

Continue reading

Posted on by fortytwo_de | Posted in ASM, C, Programación


Posted on by fortytwo_de


Estas últimas semanas he estado tomándome un pequeño descanso de Project Euler y la programación en general, pero ¡ya ha vuelto vuestra serie favorita! (no, no me lo creo ni yo).

Problema 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Mi solución a este problema es bastante naïve: compruebo si cada número entre 0 y n es primo, como en algunos problemas anteriores.

Continue reading

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