Autor
|
Tema: Criba de eratóstenes en C. (Leído 8,801 veces)
|
estudiante_1
Desconectado
Mensajes: 47
|
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: #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
Mensajes: 61
|
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
Mensajes: 625
|
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
Mensajes: 47
|
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. 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
Mensajes: 47
|
He sacado una forma de tachar los múltiplos, es esta: 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.
|
|
|
En línea
|
|
|
|
A.I.
Desconectado
Mensajes: 61
|
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. #include<stdio.h> #include <stdlib.h> int main(){ int n, i, j,aux, *l; l = (int *)calloc( n + 1, sizeof(int) ); //n+1 enteros puestos a 0 for (i = 2; i <= n; i++){ if (l[i] == 0){ //consideramos no tachados los marcados con 0 for (j = 2; ;j++){ aux = i * j; //los multiplos del numero if (aux > n) //menores o iguales a n break; l[aux] = 1; //los tachamos } } } for (i = 2; i <= n; i++) if (l[i] == 0) //si no esta tachado printf("%d ",i ); // lo imprimimos }
Advertencia - mientras estabas escribiendo, una nueva respuesta fue publicada. Probablemente desees revisar tu mensaje.
|
|
|
En línea
|
|
|
|
estudiante_1
Desconectado
Mensajes: 47
|
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
|
|
|
En línea
|
|
|
|
estudiante_1
Desconectado
Mensajes: 47
|
Me sale casi correcto, el problema es que a la salida que me da el programa me salen algunos 0. Es este: #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
Mensajes: 94
|
#include<stdio.h> main() { int n; int v[n]; int i,aux=1; printf("Los primeros %d numeros primos\n",n ); for(i=0;i<n;i++){ aux=2*aux+1; v[i]=aux; } for(i=0;i<n;i++){ } }
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
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
[C#] Criba de Eratóstenes
.NET (C#, VB.NET, ASP)
|
Hendrix
|
1
|
10,108
|
30 Septiembre 2007, 12:49 pm
por Meta
|
|
|
Criba de Eratostenes[C]
Programación C/C++
|
HRSLASH
|
1
|
9,272
|
30 Diciembre 2010, 02:46 am
por N0body
|
|
|
La criba de Operadores Móviles Virtuales continúa. Ortel Mobile es el ...
Noticias
|
wolfbcn
|
0
|
1,302
|
15 Noviembre 2013, 14:05 pm
por wolfbcn
|
|
|
Criba de Eratostenes en C con funciones.
Programación C/C++
|
estudiante_1
|
6
|
3,910
|
20 Agosto 2015, 03:16 am
por furciorifa
|
|