Criba de Eratóstenes

Criba de Eratóstenes

caeruleus 15 May 2010 16:02

Hola, había estado viendo el CyM98, más específicamente este post: http://oma.org.ar/omanet/cym98/cribaeratostenes.htm. Sobre la criba de Eratóstenes; entendí el procedimiento, pero cuando vi el código en QB, la verdad que no llegué a entenderlo del todo. Yo hice éste script en C: http://pastebin.org/240015. No sé cuál es su opinión, qué parte del código mejorar, o si está bien de esa forma.

Re: Criba de Eratóstenes

caeruleus 15 May 2010 16:05

P/D : noc porque no me deja crear un post en la seccion de usuarios :S

Re: Criba de Eratóstenes

pabloh 26 May 2010 22:22

Tanto el wiki como el foro pueden ser modificados solamente por miembros del wiki, para evitar spam. El primer paso es crear un usuario en wikidot, cosa que ya hiciste. El segundo es unirse a este wiki/foro. ¡Te invito a hacerlo!

La única excepción es la sección del foro llamada “Tema libre (casi) - Abierto”, que permite posts de cualquier persona.

Re: Criba de Eratóstenes

pabloh 27 May 2010 23:21

Bueno, para empezar, acá mando una versión en C++ equivalente a la "versión dibujada" (la simple, sin mejoras), de la lección Omanet sobre criba de Eratóstenes, que está en QB. Con algunos cambios mínimos:

• Los arrays en C y C++ empiezan en 0, y las posiciones válidas de un array “int tabla[20];” son tabla[0], tabla[1], …, tabla[19].
• En lugar de lista llamo tachado a la tabla donde vamos tachando, y en lugar de tener los valores 0 o 1, tiene true o false.
• Saqué todo el código que pone colorcitos.

#include <iostream>
int main(void)
{
    const int NMAX = 1000;
 
    //Armamos la "lista"
    bool tachado[NMAX];
    for (int i = 0; i < NMAX; ++i)
        tachado[i] = false; //empezamos con todos sin tachar
    tachado[0] = true; //0 no es primo, lo tacho
    tachado[1] = true; //1 no es primo, lo tacho
 
    //y ahora empezamos a tachar
    for (int p = 0; p < NMAX; ++p) {
        if (!tachado[p]) {
            //p no esta tachado, asi que es primo
            std::cout << p << ' ';
 
            //tachamos todos los múltiplos que estén en la "lista" o tabla
            for (int j = 2*p; j < NMAX; j += p)
                tachado[j] = true;
        }
    }
    std::cout << std::endl;
 
    return 0;
}

Re: Criba de Eratóstenes

pabloh 27 May 2010 23:37

A continuación va la versión en C++ de la “version rápida” de la lección Omanet sobre criba de Eratóstenes, que está en QB. Con las mismas modificaciones de “traducción” que arriba. Los cambios para acelerar son:

• No hace falta tachar los múltiplos de p menores a p*p (2*p, 3*p, …, (p-1)*p) porque seguro ya están tachados.
• Así que si p*p <= NMAX-1 tengo algo para tachar, en caso contrario nada hay que tachar. Así que partimos en dos casos. (La línea const int corte = static_cast<int>(floor(sqrt(static_cast<double>(NMAX-1)))); calcula la parte entera de la raíz cuadrada de NMAX-1).

#include <iostream>
#include <cmath>
int main(void)
{
    //Buscamos los primos hasta el 999
    const int NMAX = 1000;
 
    //Armamos la "lista"
    bool tachado[NMAX];
    for (int i = 0; i < NMAX; ++i)
        tachado[i] = false; //empezamos con todos sin tachar
    tachado[0] = true; //0 no es primo, lo tacho
    tachado[1] = true; //1 no es primo, lo tacho
 
    //Busco los primos chicos
    const int corte = static_cast<int>(floor(sqrt(static_cast<double>(NMAX-1))));
    for (int p = 2; p <= corte; ++p) {
        if (!tachado[p]) {
            //p no esta tachado, asi que es primo
            std::cout << p << ' ';
 
            //tachamos todos los múltiplos que estén en la "lista" o tabla
            for (int j = p*p; j < NMAX; j += p)
                tachado[j] = true;
        }
    }
 
    //Busco los primos grandes
    for (int p = corte+1; p < NMAX; ++p) {
        if (!tachado[p]) {
            //p no esta tachado, asi que es primo
            std::cout << p << ' ';
        }
    }
    std::cout << std::endl;
 
    return 0;
}

Re: Criba de Eratóstenes

pabloh 27 May 2010 23:54

Ahora comento tu código (debajo). Siempre es mejor incluirlo en el post: es más cómodo, y no dependemos de otro sitio.

#include <stdio.h>
#include <math.h>
 
main(){
 
        int n, i, x, j, max;
 
        printf("Ingresar el maximo: ");
        scanf("%d",&max);
        printf("\n");
 
        int lista[max];
 
        for (i = 0; i <= max; i++) lista[i] = i + 2;
 
        for (n = 0; n <= max; n++){
                for (x = n+1; x <= max; x++) {
                        if (lista[x] != 0 && lista[n] != 0){
                                if(lista[x] % lista[n] == 0) lista[x] = 0;
                        }
                }
        }
 
        for (j = 0; j <= max; j++){
                if (lista[j] != 0) printf("%d ",lista[j]);
        }
        printf("\n");
 
}

Algunas cosas para comentar:

• Tu código usa arrays dinámicos en C. Eso es, o bien una extensión de gcc, o bien parte de C99. Y es probable que no esté disponible durante la competencia, así que ojo con eso. Alternativas: usar arrays de tamaño constante, o usar std::vector<int> en C++.
• Como puse más arriba, las posiciones válidas del array lista son 0, …, max-1. Por lo tanto estás accediendo fuera de rango, es un error.
• Fijate que lista[n] no cambia dentro del ciclo para x. Por lo tanto la parte del if que revisa lista[n] se puede mover fuera del ciclo:

for (n = 0; n < max; n++){
        if (lista[n] != 0){
                for (x = n+1; x < max; x++) {
                        if (lista[x] != 0){
                                if(lista[x] % lista[n] == 0) lista[x] = 0;
                        }
                }
        }
}

• Por último, pero quizás lo más importante, tu ciclo para x revisa todos los números mayores a n. La clave de la criba es, justamente, no hacer eso. La idea es tachar solamente los múltiplos de n, por ejemplo ir sumando n:

for (x = 2*n; x < max; x += n)
      lista[x] = 0;

• Aplicando todos esos cambios te queda, me parece, la primer versión que mandé. Luego aplicando las dos mejoras queda la segunda versión que mandé.

Cualquier duda, posteá! :-)

Re: Criba de Eratóstenes

caeruleus 28 May 2010 01:27

Ahora lo entendí un poco mejor,muchas gracias, mañana me pondré a analizar todo con mayor detenimiento.

Algo que sí no me quedó claro ahora, es sobre lo de arrays dinámicos (?), no entiendo a qué te referís.
Uso gcc porque en mi casa tengo GNU/Linux, en el colegio no más practico con DJGPP. Estaría bueno si me pudieras decir algunas cosas q deba tener en cuenta al ir de uno a otro.

Arrays dinámicos

pabloh 30 May 2010 23:25

Los arrays, en C anterior al C99, y en C++, se definen así:

int nombre[tam];

donde int es el tipo (puede ser casi cualquier tipo), nombre es la variable, y tam es la cantidad de elementos, y tam debe ser una (expresión) constante entera. Constante definida al momento de compilar el programa. Por ejemplo cosas como:

3
3+7
const int tam = 3;
tam+1
#define tam 7

Si el tamaño es una variable (lo que llamo “array dinámico”), en C anterior a C99 y en C++ salta un error de compilación. En gcc creo que hay una extensión que permite hacerlo, y en C99 creo que se puede. Yo personalmente recomiendo usar C++ y std::vector<int>.