Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: estudiante_1 en 27 Julio 2015, 17:05 pm



Título: Criba de eratóstenes en C.
Publicado por: estudiante_1 en 27 Julio 2015, 17:05 pm
Realizar un programa que calcule los números primos entre 1 y N mediante la criba
de Eratóstenes. El sistema consiste en crear una tabla con los números del 2 a N. El
primer número no tachado (el 2) es primo. Tachar todos los múltiplos del 2. El primer
número no tachado (el 3) es primo. Tachar todos los múltiplos del 3. El primer número
no tachado (el 5) es primo. Tachar todos los múltiplos del 5.
     Mi problema es que no sé como "tachar" los múltiplos. Este es lo que yo llevo hecho:
Código:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
     int main(void){
int n;
     scanf("%d",&n);

      int v[n];
     int i;
     for(i=2;i<n;i++){
            v[i]=i;
 printf("%d\n",v[i]);
     }
     for(i=2;i<n;i++){
        if(v[i]%i!=0) printf("\n%d\n",v[i]);

     }
     system("pause");
     return(0);

     }


Título: Re: Criba de eratóstenes en C.
Publicado por: A.I. en 27 Julio 2015, 20:42 pm
Poner en la posición el valor del indice es información redundante. En lugar de hacer eso al recorrer el vector pon un 0 (no primo) o un 1 (primo). Además utilizando punteros (o simple aritmética con los indices) puedes ahorrarte bastantes operaciones.


Título: Re: Criba de eratóstenes en C.
Publicado por: Usuario Invitado en 27 Julio 2015, 21:05 pm
Yo hice lo mismo para un amigo pero en Java. Te dejo el gist para que lo veas y lo traduzcas a C: Números primos con criba de eratóstenes (https://gist.github.com/GusGarsaky/9ef810d02e1b07a9d97c)


Título: Re: Criba de eratóstenes en C.
Publicado por: estudiante_1 en 28 Julio 2015, 00:15 am
Poner en la posición el valor del indice es información redundante. En lugar de hacer eso al recorrer el vector pon un 0 (no primo) o un 1 (primo). Además utilizando punteros (o simple aritmética con los indices) puedes ahorrarte bastantes operaciones.
No entiendo lo que quieres decir, además en este problema no me dejan utilizar punteros.
Yo hice lo mismo para un amigo pero en Java. Te dejo el gist para que lo veas y lo traduzcas a C: Números primos con criba de eratóstenes (https://gist.github.com/GusGarsaky/9ef810d02e1b07a9d97c)
Soy nuevo en esto, no llevo ni un año y la verdad es que solo sé "manejar" C.
Gracias de todos modos.


Título: Re: Criba de eratóstenes en C.
Publicado por: estudiante_1 en 28 Julio 2015, 00:35 am
He sacado una forma de tachar los múltiplos, es esta:
Código:
for(i=2;i<n;i++){
      for(j=2;i*j<n;j++){
         printf(" Este no es primo %d\n",v[i*j]);
      }
     }
El problema es que no se me ocurre como imprimir los que sí son primos. Una ayudita por favor. :rolleyes:


Título: Re: Criba de eratóstenes en C.
Publicado por: A.I. en 28 Julio 2015, 00:41 am
Cómo te veo bastante perdido te pongo un código sencillito, es bastante auto explicativo pero si tienes alguna duda pregunta. Cómo no puedes usar punteros puedes sustituir la parte del calloc por crearte un vector y rellenarlo tú. Sobre todo compáralo con lo que tenías tú escrito y con lo que tenías en mente a la hora de implementarlo.

Código
  1. #include<stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(){
  5. int n, i, j,aux, *l;
  6.  
  7. scanf("%d",&n);
  8. l = (int *)calloc( n + 1, sizeof(int) ); //n+1 enteros puestos a 0
  9.  
  10. for (i = 2; i <= n; i++){
  11.  
  12. if (l[i] == 0){ //consideramos no tachados los marcados con 0
  13. for (j = 2; ;j++){
  14. aux = i * j; //los multiplos del numero
  15. if (aux > n) //menores o iguales a n
  16. break;
  17. l[aux] = 1; //los tachamos
  18. }
  19. }
  20. }
  21.  
  22.  
  23. for (i = 2; i <= n; i++)
  24. if (l[i] == 0) //si no esta tachado
  25. printf("%d ",i); // lo imprimimos
  26. }


Advertencia - mientras estabas escribiendo, una nueva respuesta fue publicada. Probablemente desees revisar tu mensaje.


Título: Re: Criba de eratóstenes en C.
Publicado por: estudiante_1 en 28 Julio 2015, 00:48 am
Vale, aunque no entiendo muy bien  tu programa, me gustaría hacerlo como he pensado.  Dime que sabes que tengo  que hacer para que me imprima los que sí son primos :silbar:


Título: Re: Criba de eratóstenes en C.
Publicado por: estudiante_1 en 28 Julio 2015, 01:39 am
Me sale casi correcto, el problema es que a la salida que me da el programa me salen algunos 0. Es este:
Código:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
     int main(void){
int n;
     scanf("%d",&n);

      int v[n];
     int i;
     for(i=2;i<n;i++){
            v[i]=i;
 printf("%d\n",v[i]);
     } int j;

     for(i=2;i<n;i++){
      for(j=2;i*j<n;j++){
v[i*j]=0;
      }if (v[i]!=v[i*j]){

      printf("\nNumeros primos: %4d\n",v[i]);
      }
     }




     system("pause");
     return(0);

     }


Título: Re: Criba de eratóstenes en C.
Publicado por: furciorifa en 19 Agosto 2015, 22:59 pm
Código
  1. #include<stdio.h>
  2. main()
  3. {
  4.  
  5. int n;
  6.  
  7. scanf("%d",&n);
  8.  
  9. int v[n];
  10.  
  11. int i,aux=1;
  12. printf("Los primeros %d numeros primos\n",n);
  13. for(i=0;i<n;i++){
  14. aux=2*aux+1;
  15. v[i]=aux;
  16.  
  17. }
  18.  
  19. for(i=0;i<n;i++){
  20. printf(" [%d]",v[i]);
  21. }
  22. printf("\n");
  23. }
  24.  

Esta es la respuesta más fácil que se me ocurre utilizando arreglos, la otra manera todavía más fácil es haciendo un for sin arreglos e imprimir un 2*n +1 que es un número impar por definición.