• Viernes 8 de Noviembre de 2024, 22:57
« anterior próximo »
Páginas: [1]

Autor Tema:  Eratostenes  (Leído 1551 veces)

ermiguel1979

  • Miembro activo
  • **
  • Mensajes: 45
    • Ver Perfil
Eratostenes
« en: Jueves 6 de Mayo de 2010, 13:58 »
0
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!!

Epa

  • Miembro MUY activo
  • ***
  • Mensajes: 242
  • Nacionalidad: ar
    • Ver Perfil
Re: Eratostenes
« Respuesta #1 en: Jueves 6 de Mayo de 2010, 17:59 »
0
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
The sweet smell of a great sorrow lies over the land.

ermiguel1979

  • Miembro activo
  • **
  • Mensajes: 45
    • Ver Perfil
Re: Eratostenes
« Respuesta #2 en: Sábado 12 de Junio de 2010, 20:16 »
0
Gracias por tu ayuda, lo pongo en práctica.

Un saludo!!

bavarol

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
Re: Eratostenes
« Respuesta #3 en: Martes 22 de Junio de 2010, 08:43 »
0
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.  
Páginas: [1]
« anterior próximo »