elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Introducción a Git (Primera Parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Criba de eratóstenes en C.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Criba de eratóstenes en C.  (Leído 6,656 veces)
estudiante_1

Desconectado Desconectado

Mensajes: 47


Ver Perfil
Criba de eratóstenes en C.
« 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);

     }


En línea

A.I.

Desconectado Desconectado

Mensajes: 61


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #1 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.


En línea

Usuario Invitado


Desconectado Desconectado

Mensajes: 625



Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #2 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
En línea

"La vida es muy peligrosa. No por las personas que hacen el mal, si no por las que se sientan a ver lo que pasa." Albert Einstein
estudiante_1

Desconectado Desconectado

Mensajes: 47


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #3 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
Soy nuevo en esto, no llevo ni un año y la verdad es que solo sé "manejar" C.
Gracias de todos modos.
En línea

estudiante_1

Desconectado Desconectado

Mensajes: 47


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #4 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:
En línea

A.I.

Desconectado Desconectado

Mensajes: 61


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #5 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.
En línea

estudiante_1

Desconectado Desconectado

Mensajes: 47


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #6 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:
En línea

estudiante_1

Desconectado Desconectado

Mensajes: 47


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #7 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);

     }
En línea

furciorifa

Desconectado Desconectado

Mensajes: 94


Ver Perfil
Re: Criba de eratóstenes en C.
« Respuesta #8 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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[C#] Criba de Eratóstenes
.NET (C#, VB.NET, ASP)
Hendrix 1 9,030 Último mensaje 30 Septiembre 2007, 12:49 pm
por Meta
Criba de Eratostenes[C]
Programación C/C++
HRSLASH 1 8,453 Último mensaje 30 Diciembre 2010, 02:46 am
por N0body
La criba de Operadores Móviles Virtuales continúa. Ortel Mobile es el ...
Noticias
wolfbcn 0 579 Último mensaje 15 Noviembre 2013, 14:05 pm
por wolfbcn
Criba de Eratostenes en C con funciones.
Programación C/C++
estudiante_1 6 2,995 Último mensaje 20 Agosto 2015, 03:16 am
por furciorifa
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines