SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: ermiguel1979 en Jueves 6 de Mayo de 2010, 13:58

Título: Eratostenes
Publicado por: ermiguel1979 en Jueves 6 de Mayo de 2010, 13:58
Un saludo a todos.
Tengo problemas para realizar un ejercicio sobre la criba de Eratóstenes que dice así:
La criba de Eratóstenes es una técnica para generar números primos. Se comienza escribiendo todos los enteros impares desde 3 hasta N; luego se elimina cada tercer elemento después de 3, cada quinto elemento despues de 5..., hasta que los múltiplos de todos los enteros impares menores de "la raiz cuadrada de N" hayan sido eliminados.

Mi problema está en que no cosigo eliminar dichos múltiplos. Deben aparecer en el vactor como -1.

Aquí está lo que llevo realizado:

Código: C
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. int main (void){
  6.    
  7.     int N;                  
  8.    
  9.     int i;
  10.     int impar;
  11.     int vector[50];
  12.     int a=3;                
  13.    
  14.     printf("Indique el numero final (impar) N:");
  15.     scanf("%i", &N);
  16.    
  17.     for(i=0; i<=49; i++){
  18.         vector[i]=0;
  19.     }
  20.    
  21.    
  22.     for(i=0; i<=N; i++){
  23.         impar=2*((i+1)-1)+3;
  24.         if(impar<=N){
  25.             vector[i]=impar;
  26.         }
  27.     }
  28.    
  29.    
  30.     for(i=0; i<=N; i++){
  31.         if(vector[i]!=0){
  32.             printf(" %i", vector[i]);
  33.         }
  34.     }
  35.     printf("n");
  36.    
  37.    
  38.    
  39.     int j, k;
  40.     float b=sqrt(N);
  41.    
  42.        
  43.     for(j=0; j<=N; j++){
  44.         for(k=0; k<=N; k++){
  45.             if(vector[i]!=a && vector[i]<b && vector[i]%a==0){
  46.                 vector[i]=-1;
  47.             }
  48.         }
  49.         a=a+2;
  50.     }
  51.    
  52.    
  53.     for(i=0; i<=N; i++){
  54.         printf(" %i", vector[i]);
  55.     }
  56.     printf("n");
  57.    
  58.    
  59.    
  60.    
  61.     return 1;
  62. }
  63.  

Gracias a todos!!
Título: Re: Eratostenes
Publicado por: Epa en Jueves 6 de Mayo de 2010, 17:59
Buenas


creo que esto implementa lo que decis al principio:


Código: C++
  1.  
  2. int i,j,N=800;
  3. int vec[800];
  4.  
  5. for(i = 0; i < N; i++)
  6.     vec[i] = 2*(i+1)+1;
  7.  
  8. for(i = 0; i < sqrt(N); i++)
  9.     if(vec[i] != -1)
  10.         for(j = (i + vec[i]); j < N; j += vec[i])
  11.             vec[j] = -1;
  12.  
  13. for(i=0; i<N; i++)
  14.     if(vec[i] != -1) printf(" %i", vec[i]);
  15.  
  16.  
  17.  

Primero lleno el vector con los numeros impares, despues recorro el vector buscando los numeros que no tache, desde la posicion 0 hasta la raiz de N, despues desde la posision del SIGUIENTE multiplo del numero actual recorro el vector incrementando tantos lugares como el numero que busco los multiplos y lo cambio por -1.

Espero se entienda la idea

Saludos
Título: Re: Eratostenes
Publicado por: ermiguel1979 en Sábado 12 de Junio de 2010, 20:16
Gracias por tu ayuda, lo pongo en práctica.

Un saludo!!
Título: Re: Eratostenes
Publicado por: bavarol en Martes 22 de Junio de 2010, 08:43
Queria puntualizar que ese ejercicio de primer curso de programacion que hice en mi tiempo no decia nunca el tamanio de la muestra, esto es, acababa en un 0 o en un fin de linea, asi pues, las limitaciones que os haceis vosotros mismos en el tamanio no vienen al caso
[Me ahorrare declaraciones y todo eso, de acuerdo?]
 
Código: C++
  1. cout << "Introduzca el tope de la criba: ";
  2. cin >> tope;
  3.  
  4. /* Inicializacion */
  5. criba = new bool[tope + 1];
  6.  
  7. criba[0] = false;
  8.  
  9. for(int i = 1; i <= tope; ++i) criba[i] = true;
  10.  
  11.  /* ____ La criba propiamente dicha */
  12. for(int i = 2; i*i <= tope; ++i)
  13.       if(criba[i])
  14.     for(int j = 2; i*j <= tope; ++j)
  15.         criba[i*j] = false;
  16.  
  17. /* _______ Mostrar o Almacenar */
  18.  
  19. for(int i = 2; i <= tope; ++i)
  20.      /* Esto muestra, si quereis almacenar los primos en vez de sacarlos por pantalla almacenadlos convenientemente como ya sabeis  */ 
  21.     if(criba[i]) cout << i << ' ';
  22.  
  23. cout << endl;
  24.  
  25. ...
  26.  
  27.  
  28.  
  29.