Criba de eratóstenes en C.

[estudiante_1]

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 [Seleccionar] Expandir

#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);

     }


[A.I.]

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.

[Usuario Invitado]

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

[estudiante_1]

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.

[estudiante_1]

He sacado una forma de tachar los múltiplos, es esta:

Código [Seleccionar] Expandir

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.

[A.I.]

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 (c) [Seleccionar] Expandir

#include<stdio.h>
#include <stdlib.h>

int main(){
int n, i, j,aux, *l;

scanf("%d",&n);
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.

[estudiante_1]

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

[estudiante_1]

Me sale casi correcto, el problema es que a la salida que me da el programa me salen algunos 0. Es este:

Código [Seleccionar] Expandir

#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);

     }


[furciorifa]

Código (c) [Seleccionar] Expandir

#include<stdio.h>
main()
{

int n;

scanf("%d",&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++){
printf(" [%d]",v[i]);
}
printf("\n");
}


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.