Criba de Eratostenes[C]

[HRSLASH]

Hola gente! Dejo un algoritmo q devuelve numeros primos entre 1 y 1000..
Saludos!!

Código (c) [Seleccionar] Expandir


#include<stdio.h>
#define SIZE 1000

void cribaDeEratostenes(int [], int , int);

main()
{
      int vectorPrimo[SIZE];
      int i, num;
     
      for (i = 1; i <= SIZE; i++)
          vectorPrimo[i] = 1;
     
      for (i = 2; i <= SIZE; i++)
          if (vectorPrimo[i] == 1){
             cribaDeEratostenes(vectorPrimo, i, SIZE);
             printf("%-5d", i);
          }


      return 0;
}





void cribaDeEratostenes(int v[], int n, int size)
{
     int i = n;
     
     for (i += n; i <= size; i += n)
         v[i] = 0;
}


[N0body]

:O esto merece un comentario, creo q en uno de los primeros post q hice en el foro se trataba sobre la Criba de Eratostenes...

Algunas acotaciones bobas:

-en tu caso hiciste una correspondencia entre la posicion en el vector y el numero que representa dicho "hueco" de la criba... haciendo esto desperdicias 2 numeros... ya que el 1 y el 0 no los necesitas en el análisis y sí son posibles "i" (posiciones). Esto podria solucionarse haciendo que la posicion "i" (o el hueco "i" del vector q representa la criba como me gusta llamarlo) represente al número i+2... de ese modo no desperdiciar 2 numeros... En cualquier caso, en el primer bucle (el que llena todo con "1") llenas la posicion 1 que no necesitas porque no usas.

-Yo no usaria una funcion, es algo inecesario, la incluyes en un bucle, la llamas muchisimas veces (depende de la longitud de la criba), es preferible escribir todo en el bucle mismo y evitarse todo los pasos q consisten en el paso de argumentos... hasta le haces un favor seguramente (y mientras este prolijo) a cualquiera q lo lea (y a ti mismo, escribes menos). Además (y si todavía te ostinas con utilizar funciones) lo que está definido en el define (si mal no recuerdo) vale para todo el código, es un desperdicio que pases como argumento dicha constante...

-El vector representa un "estado" de los numeros que se identifican con su posicion. Traducido: el número 13 se ve representado por el entero vectorPrimo[13]... lo que esta adentro de esa variable, osea, el valor de vectorPrimo[13] indica meramente un estado logico del numero, osea indica si es primo o no... por lo tanto y para ahorrar memoria yo usaria un vector char en vez de un int (dado que estas almacenando solo 1 y 0).

-En el programa cuando encuentras un primo "x" tachas todos los multiplos de "x"... Pero te olvidas que ya habias encontrado primos menores que "x" y que tachaste los multiplos de estos... muchos de estos seran tambien multiplos de "x" que volveras a revisar... mejor yo diria que en el bucle de la funcion empieces a tachar los multiplos de x a partir de x*x en vez de 2*x...

Espero que se me entienda, sé que no tengo la mejor ortografía y que a veces mis oraciones se extienden demasiado...

Próspero año nuevo!