Publi

Generador de números primos en C

Un ejercicio de estos típicos de lenguaje C, es la generación de números primos y la comprobación de éstos. Ni que decir tiene que esta es sólo una de las 13.485,72 maneras (o más) de solucionar este problema. Y es más estamos complicando un poco la cosa, ya que sólo generaremos 10 números, que se almacenarán en un fichero binario, y a la siguiente vez que ejecutamos el programa, se leerá ese último número y seguiremos generando primos a partir de ahí:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <math.h>

// Comprobamos si un número es primo o no
int es_primo(int numero)
{
  int res=0;
  int divs=2;
  int mitad;
  if (numero>2)    // Si el número es mayor a 2, comprobamos si es primo.
    {
      /* Para ahorrar sólo comprobamos si un número es divisible hasta su mitad, ya que 7/2 = 3.xxx, 7/3=2.xxx, 7/4=0.xxx */
      /* cuando empezamos a obtener valores menores que 0, ya no encontraremos más divisores enteros */
      mitad=floor((double)numero/2);
      do
    {
      res=(numero%divs!=0);  /* ¿ El resto es 0 ? */
      //      printf("Divido %d entre %d. Resto %d. Res: %d\n", numero, divs, numero%divs, res);
      divs++;
    } while ((res!=0) && (divs<=mitad));
    }
  else if (numero==2) /* || (numero==1) */ /* ¿1 lo consideramos primo? */
    res=1;

  return res;
}

// Genera primos, los almacenaremos en p, empezamos desde _inicial_ y generamos _cantidad_ de números
void genera_primos (FILE *p, int inicial, int cantidad)
{
  int primos=0;
  int i=inicial;

  printf("INI:%d\n", inicial);
  while (primos<cantidad)
    {
      // Vamos comprobando uno a uno si es primo
      if (es_primo(i))
    {
      fwrite(&i, sizeof(int), 1, p);
      primos++;
      printf("%d\n", i);
    }
      i++;
    }
}


int main()
{
  FILE *p;
  int last_primo;
  // Abrimos el archivo para actualizar
  p = fopen("primos.dat", "a+b");
  if (p)
    {
      fseek(p, -sizeof(int), SEEK_END); /* Nos posicionamos para leer el último entero almacenado. */
      fread(&last_primo, sizeof(int), 1, p); /* Leemos el último */
      fseek(p, 0, SEEK_END); /* Nos posicionamos al final, para seguir escribiendo */
      printf("%d: ",last_primo);
      genera_primos(p, last_primo+1, 10);
      fclose(p);
    }
  else
    printf("No puedo abrir el archivo");
}

De aquí se pueden extraer ideas para hacer muchos ejercicios de este tipo. Eso sí, hay que recordar que para compilar tenemos que incluir la librería matemática. Por ejemplo, con gcc, en el caso de llamar al archivo primos.c, se compilaría:

gcc -lm -o primos primos.c

También podría interesarte....

There are 3 comments left Ir a comentario

  1. Pingback: Bitacoras.com /

  2. ivan /
    Usando Mozilla Firefox Mozilla Firefox 3.5.3 en Windows Windows XP

    Se acerca ala forma tradicional de generarlos, que es lento, pero entendible, estoy buscando mejores formas, he visto las cribas y son mejor forma de generar, hasta encontre una criba especial mas eficiente pero no encontrado una de atkin para compararla que funcione visula c, no conozco mucho del lenguaje y las que he bajado me dan errores. Si Alguien tiene una para probar compatible con visual c, me la puede mandar a IvanMrsnik@gmail.com, por lo momentos 600 millones de valores me los prueba en 14 segundos en una laptop lenovo n200, me he parado ahi debido a problemas de memoria voy hacer un cambio que no utiliza casi memoria, dentro de poco, tal vez se ponga mas lento pero sacara muchos mas.

  3. admin / Post Author
    Usando Mozilla Firefox Mozilla Firefox 3.6 en Linux Linux

    @ivan
    Quiero ponerme un día de estos a probar cómo podría generar los números con la criba. El método aquí propuesto debía ser más intuitivo, era la resolución a un problema propuesto de uno de mis alumnos.

Leave a Reply to ivan Cancle Reply