primos2.c

  1. /*
  2.  * PRIMOS v2.0
  3.  * Calcula los números primos.
  4.  *
  5.  * Francisco Cascales, junio-1999
  6.  * Compilado con DJGPP http://www.delorie.com/djgpp/
  7.  *
  8.  * Adaptado para GCC, Diciembre-2017
  9.  * $ gcc primos.c -o primos.exe
  10.  * $ ./primos.exe -c
  11.  *
  12.  * ERRORES:
  13.  * $ ./primos.exe -f 55555555 --> 5*11*73*137 (Falta el 101)
  14.  *
  15.  * Los números primos son aquellos
  16.  * números que tan sólo son divisibles
  17.  * por sí mismos y por la unidad.
  18.  * El cero y el uno no son primos (30/7/99).
  19.  *
  20.  * TABLAS COMPARATIVAS de velocidad de cálculo
  21.  * y memoria requerida con los distintos métodos
  22.  * de calcular los primos en un Pentium-II a 350MHz
  23.  *
  24.  * 10.000 primos (último primo 104.729)
  25.  * -----------------------------------
  26.  * Método #1 7 seg. 40.000 bytes
  27.  * Método #2 0 seg. 104.724 bytes
  28.  * Método #3 0 seg. 13.090 bytes
  29.  *
  30.  * 100.000 primos (último primo 1.299.709)
  31.  * ---------------------------------------
  32.  * Método #1 755 seg. 400.000 bytes
  33.  * Método #2 0 seg. 1.299.690 bytes
  34.  * Método #3 0 seg. 162.464 bytes
  35.  *
  36.  *
  37.  * Método #3
  38.  * primos tiempo bytes últ. primo
  39.  * --------------------------------------------------
  40.  * 1.000.000 7 seg. 1.935.736 15.485.863
  41.  * 10.000.000 105 seg. 22.428.088 179.424.673
  42.  */
  43.  
  44.  
  45.  
  46. #include <stdio.h>
  47. #include <time.h>
  48. #include <string.h>
  49.  
  50. #include <ctype.h> // isdigit
  51.  
  52.  
  53. #define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
  54.  
  55.  
  56. //-----------------------------------------------
  57. // TIPOS DE DATOS
  58.  
  59.  
  60. typedef unsigned char byte; // De 8 bits
  61. typedef unsigned long int dword; // De 32 bits
  62. typedef enum {false, true} bool; // De 1 bit
  63.  
  64.  
  65. //-----------------------------------------------
  66. // VARIABLES GLOBALES
  67.  
  68.  
  69. const char archivoBit [] = "PRIMOS.BIT"; // Imagen del vector de bits
  70. const char archivo110 [] = "PRIMOS.110"; // Comprimido contando unos seguidos
  71.  
  72.  
  73. //-----------------------------------------------
  74. // CONMUTADORES
  75.  
  76.  
  77. //#define METODO1
  78. //#define METODO2
  79. #define METODO3
  80.  
  81.  
  82. //-----------------------------------------------
  83. // FUNCIONES DE USO GENERAL
  84.  
  85. /**
  86.  * Invierte una cadena.
  87.  * Ejemplo: "PEPITO" pasa a ser "OTIPEP".
  88.  * Uso : printf ("%s", reverse("PEPITO"));
  89.  */
  90. char *reverse (char *cadena)
  91. {
  92. char *inicio = cadena;
  93. char *fin = cadena + strlen(cadena) - 1;
  94.  
  95. while (inicio < fin)
  96. {
  97. char temp = *inicio;
  98. *inicio = *fin;
  99. *fin = temp;
  100.  
  101. ++inicio;
  102. --fin;
  103. }
  104. return cadena;
  105. }
  106.  
  107. /**
  108.  * Convierte un número entero en cadena
  109.  * incluyendo puntos de millares.
  110.  *
  111.  * Ejemplo: 1234567 pasa a ser "1.234.567"
  112.  * Uso : printf ("%s", str (1234567));
  113.  * Nota : el buffer devuelto siempre es
  114.  * el mismo.
  115.  */
  116. char *str (dword num)
  117. {
  118. static char cadena [25];
  119. int i = 0;
  120. int cifras = 0;
  121. int trio=0;
  122.  
  123. for (;;)
  124. {
  125. byte digito = num % 10;
  126. cadena[i++] = digito + '0';
  127. num /= 10;
  128.  
  129. if (num == 0) break;
  130.  
  131. if (++trio == 3)
  132. {
  133. cadena[i++] = '.';
  134. trio = 0;
  135. }
  136. }
  137. cadena[i] = '\0';
  138.  
  139. return reverse (cadena);
  140. }
  141.  
  142. /**
  143.  * Convierte una cadena con puntos
  144.  * de millares en un número entero.
  145.  *
  146.  * Ejemplo: "1.234.567" pasa a ser 1234567
  147.  * Uso : printf ("%u", dw ("1.234.567"));
  148.  */
  149. dword dw (char *str)
  150. {
  151. dword num=0;
  152. char *s;
  153.  
  154. for (s=str; *s; ++s)
  155. {
  156. if (isdigit (*s))
  157. {
  158. num = num*10 + (*s - '0');
  159. }
  160. else if (*s == '.')
  161. {
  162. continue;
  163. }
  164. else
  165. {
  166. break;
  167. }
  168. }
  169. return num;
  170. }
  171.  
  172.  
  173. /**
  174.  * Cada segundo muestra un carácter nuevo
  175.  * en pantalla.
  176.  * Se usa dentro del bucle de un algoritmo
  177.  * que requiera mucho tiempo de proceso.
  178.  * Así el usuario percibe que el ordenador
  179.  * no se ha quedado bloqueado.
  180.  */
  181. void ElTiempoNoPasaEnBalde ()
  182. {
  183. #if 1
  184. static clock_t startTime = 0;
  185. static char c = '*';
  186. clock_t endTime = clock ();
  187.  
  188. // Si ha pasado un segundo...
  189. if ((endTime-startTime)/CLOCKS_PER_SEC >= 1)
  190. {
  191. startTime = endTime;
  192. printf("%c", c); //putch (c);
  193. //gotoxy (wherex ()-1, wherey()); // El carácter en el mismo sitio
  194. c = (c == '*') ? '-' : '*';
  195. }
  196. #endif
  197. }
  198.  
  199. /**
  200.  * Intercambia los valores entre num1 y num2
  201.  */
  202. void swap (dword *num1, dword *num2)
  203. {
  204. dword temp = *num1;
  205. *num1 = *num2;
  206. *num2 = temp;
  207. }
  208.  
  209. //-----------------------------------------------
  210. // METODO #1 DE CALCULAR PRIMOS (muy lento)
  211.  
  212. #ifdef METODO1
  213.  
  214. /*
  215.  * Para calcular 100.000 números primos:
  216.  * - Se realizaron 711.547.190 iteraciones.
  217.  * - Se tardó 755 segundos (12'35")
  218.  * - Memoria necesaria 400.000 bytes
  219.  * - Ultimo primo calculado 1.299.689
  220.  */
  221.  
  222. //#define NUM_PRIMOS 100000 // cien mil
  223. //#define NUM_PRIMOS 10000 // diez mil
  224. //#define NUM_PRIMOS 1000 // mil
  225. #define NUM_PRIMOS 100 // cien
  226.  
  227. dword primos [NUM_PRIMOS]; // Vector de primos
  228.  
  229. /**
  230.  * Calcula los números primos y los
  231.  * va almacenando en un vector hasta
  232.  * que éste se llena.
  233.  */
  234. void CalcularPrimosMetodo1 ()
  235. {
  236. typedef enum { FALSO, CIERTO } logico;
  237.  
  238. // Variables de cálculo
  239. logico esPrimo;
  240. dword totPrimos = 0;
  241. dword num;
  242. dword i;
  243.  
  244. // Variables de información
  245. dword iteraciones = 0;
  246. clock_t startTime, endTime;
  247.  
  248.  
  249. printf("\nCalculando %s números primos...\n\n", str (NUM_PRIMOS));
  250.  
  251. startTime = clock ();
  252.  
  253. for (num=2; /* siempre */; ++num) // Por cada número,...
  254. {
  255. esPrimo = CIERTO; // suponer que es primo,...
  256.  
  257. // y probar si es divisible por los
  258. // primos ya encontrados hasta ahora,
  259. // excluyendo el primo 1
  260.  
  261. for (i=0; i<totPrimos; ++i)
  262. {
  263. ++iteraciones;
  264.  
  265. if ((num % primos[i]) == 0) // Si es divisible...
  266. {
  267. esPrimo = FALSO; // ...no es primo.
  268. break;
  269. }
  270. }
  271.  
  272. ElTiempoNoPasaEnBalde ();
  273.  
  274. if (esPrimo == CIERTO) // Anotar el primo encontrado
  275. {
  276. primos[totPrimos++] = num;
  277.  
  278. if (totPrimos == NUM_PRIMOS)
  279. {
  280. break; // Ya no caben más primos
  281. }
  282.  
  283. }
  284. }
  285. endTime = clock ();
  286.  
  287. printf ("\n\nLos números primos son (método #1):\n\n");
  288. for (i = 0; i<totPrimos; ++i)
  289. {
  290. printf ("%10u", primos[i]); // 8*10=80 columnas
  291. }
  292.  
  293. printf ("\n\nEn total hay %u números primos.\n", totPrimos);
  294. printf ("Se realizaron %u iteraciones.\n", iteraciones);
  295. printf ("Se tardó %u segundos.\n", (endTime-startTime)/CLOCKS_PER_SEC);
  296. printf ("Memoria necesaria %u bytes.\n", sizeof(primos));
  297.  
  298. }
  299. #endif // METODO1
  300.  
  301.  
  302. //-----------------------------------------------
  303. // METODO #2 DE CALCULAR PRIMOS (rápido pero gasto mucha memoria)
  304.  
  305. #ifdef METODO2
  306.  
  307. //#define SIZE (1299689+1) // Primo número 99.999
  308. //#define SIZE (611951+1) // Primo número 49.999
  309. //#define SIZE (104723+1) // Primo número 9.999
  310. #define SIZE (7907+1) // Primo número 999
  311.  
  312. char numeros [SIZE]; // Vector de números
  313.  
  314. /**
  315.  * Criba de Eratóstenes
  316.  * Se utiliza un vector para anotar
  317.  * si un número es o no es primo.
  318.  * Se desperdicia mucha memoria porque
  319.  * por cada número se utiliza un byte
  320.  * en lugar de un bit.
  321.  */
  322. void CalcularPrimosMetodo2 ()
  323. {
  324. typedef enum { PRIMO, TACHADO } estado;
  325.  
  326. // Variables de cálculo
  327. dword num;
  328. dword criba = 2;
  329.  
  330. // Variables de información
  331. dword totPrimos;
  332. dword iteraciones = 0;
  333. clock_t startTime, endTime;
  334.  
  335.  
  336. printf("\nCalculando los primos entre 1 y %s ...\n\n", str (SIZE-1));
  337.  
  338. startTime = clock ();
  339.  
  340. // Suponemos que todos son primos
  341. for (num=0; num<SIZE; ++num)
  342. {
  343. numeros[num] = PRIMO;
  344. ++iteraciones;
  345. }
  346.  
  347. // El 0 y el 1 no son primos
  348. numeros[0] = TACHADO;
  349. numeros[1] = TACHADO;
  350.  
  351. // Empezamos a tachar de 2 en 2
  352. // luego de 3 en 3, de 5 en 5, etc.
  353.  
  354. for (criba=2; criba<SIZE; /* nada */)
  355. {
  356. for (num=criba*2; num<SIZE; num+=criba)
  357. {
  358. numeros[num] = TACHADO;
  359.  
  360. ++iteraciones;
  361.  
  362. }
  363.  
  364. ElTiempoNoPasaEnBalde ();
  365.  
  366. // Incrementar la criba hasta encontrar
  367. // un número que no esté tachado
  368. do
  369. {
  370. ++criba;
  371.  
  372. ++iteraciones;
  373. }
  374. while (numeros[criba] == TACHADO);
  375. }
  376.  
  377.  
  378. endTime = clock ();
  379.  
  380.  
  381. //printf ("\n\nLos números primos son (método #2):\n\n");
  382. for (num=1, totPrimos=0; num<SIZE; ++num)
  383. {
  384. if (numeros[num] == PRIMO)
  385. {
  386. printf ("%10u", num); // 8*10=80 columnas
  387. ++totPrimos;
  388. }
  389. }
  390.  
  391. printf ("\n\nEn total hay %u números primos.\n", totPrimos);
  392. printf ("Se realizaron %u iteraciones.\n", iteraciones);
  393. printf ("Se tardó %u segundos.\n", (endTime-startTime)/CLOCKS_PER_SEC);
  394. printf ("Memoria necesaria %u bytes.\n", sizeof(numeros));
  395.  
  396. }
  397.  
  398. #endif // METODO2
  399.  
  400.  
  401. //-----------------------------------------------
  402. // METODO #3 DE CALCULAR PRIMOS (rápido y usa poca memoria)
  403.  
  404. #ifdef METODO3
  405.  
  406. /* Un DWORD tiene 4 bytes = 32 bits (32=2^5)
  407.  * Si tenemos un array de DWORD y queremos hacer
  408.  * referencia con un índice a un determinado bit.
  409.  * Los 5 últimos bits del índice indicarian el bit
  410.  * de un elemento del array. Y los 27 bits restantes
  411.  * sirven para indexar el elemento del array.
  412.  */
  413.  
  414. //#define NUM_BITS 64 // Pruebas
  415.  
  416. //#define NUM_BITS (100000000) // Cien millones (59 seg)
  417.  
  418. #define NUM_BITS (179424673+1) // Primo diez millones (105 seg)
  419. //#define NUM_BITS (15485857+1) // Primo un millon (7 seg)
  420. //#define NUM_BITS (1299689+1) // Primo cien mil
  421. //#define NUM_BITS (611951+1) // Primo cincuenta mil
  422. //#define NUM_BITS (104723+1) // Primo diez mil
  423. //#define NUM_BITS (7907+1) // Primo mil
  424.  
  425. #define NUM_DWORDS (((NUM_BITS-1) >> 5) + 1) // (NUM_BITS-1)/32 + 1
  426.  
  427. dword bitArray [NUM_DWORDS]; // Vector de bits
  428.  
  429. // Para depurar
  430. //#define INDEX(n) (n >> 5) // N/32
  431. //#define BIT(n) (0x00000001 << (n & 0x0000001F)) // 1 << (N%32)
  432.  
  433. /* Macros para operar sobre el vector de bits:
  434.  *
  435.  * CLEAR_BIT(n) Pone a 0 el bit indicado.
  436.  * SET_BIT(n) Pone a 1 el bit indicado.
  437.  * TEST_BIT(n) Comprueba si es 1 el bit indicado.
  438.  */
  439. #define CLEAR_BIT(n) bitArray [n >> 5] &= ~(0x00000001 << (n & 0x0000001F))
  440. #define SET_BIT(n) bitArray [n >> 5] |= (0x00000001 << (n & 0x0000001F))
  441. #define TEST_BIT(n) (bitArray [n >> 5] & (0x00000001 << (n & 0x0000001F)))
  442.  
  443. /**
  444.  * Criba de Eratóstenes
  445.  * Se utiliza un vector de bits para anotar
  446.  * si un número es o no es primo.
  447.  */
  448. void CalcularPrimosMetodo3 ()
  449. {
  450.  
  451. // Variables de cálculo
  452. dword i;
  453. dword num;
  454. dword criba = 2;
  455.  
  456. // Variables de información
  457. dword totPrimos;
  458. dword iteraciones = 0;
  459. clock_t startTime, endTime;
  460.  
  461. // Variables de depuración
  462. //dword index;
  463. //dword bit;
  464.  
  465.  
  466. printf("\nCalculando los primos entre 1 y %s ...\n\n", str (NUM_BITS-1));
  467.  
  468. startTime = clock ();
  469.  
  470.  
  471. // Suponemos que todos son primos (nada tachado)
  472. for (i=0; i<NUM_DWORDS; ++i)
  473. {
  474. bitArray [i] = 0x00000000;
  475. ++iteraciones;
  476. }
  477.  
  478. // El 0 y el 1 no son primos
  479. SET_BIT(0);
  480. SET_BIT(1);
  481.  
  482. // Empezamos a tachar de 2 en 2
  483. // luego de 3 en 3, de 5 en 5, etc.
  484.  
  485. for (criba=2; criba<NUM_BITS; ++criba)
  486. {
  487. if (!TEST_BIT(criba)) // Si no está tachado
  488. {
  489. for (num=(criba<<1); num<NUM_BITS; num+=criba)
  490. {
  491. //index = INDEX(num);
  492. //bit = BIT(num);
  493.  
  494. SET_BIT(num); // Tachar el número
  495.  
  496. ++iteraciones;
  497. }
  498. ElTiempoNoPasaEnBalde ();
  499. }
  500. }
  501.  
  502. endTime = clock ();
  503.  
  504. //printf ("\n\nLos números primos son (método #3):\n\n");
  505. for (num=1, totPrimos=0; num<NUM_BITS; ++num)
  506. {
  507. if (!TEST_BIT(num))
  508. {
  509. //if ((NUM_BITS - num) < 1000) // Imprimir sólo los últimos primos
  510. //printf ("%10u", num); // 8*10=80 columnas
  511. ++totPrimos;
  512. }
  513. }
  514.  
  515. printf ("\n\nEn total hay %s números primos.\n", str (totPrimos));
  516. printf ("Se realizaron %s iteraciones.\n", str (iteraciones));
  517. printf ("Se tardó %ld segundos.\n", ((endTime-startTime)/CLOCKS_PER_SEC));
  518. printf ("Memoria necesaria %s bytes.\n", str (sizeof(bitArray)));
  519.  
  520. }
  521. #endif
  522.  
  523. //-----------------------------------------------
  524. // GUARDAR Y RECUPERAR PRIMOS EN UN ARCHIVO
  525.  
  526. /**
  527.  * Guarda el vector que indica los primos
  528.  * en el disco duro.
  529.  *
  530.  * Si son 100.000.000 de números
  531.  * el archivo ocupa 12.500.000 bytes
  532.  */
  533. int GuardarArchivoPrimos ()
  534. {
  535. FILE *f;
  536. dword bytes;
  537.  
  538. f = fopen (archivoBit, "wb");
  539.  
  540. if (f==NULL)
  541. {
  542. printf ("\nNo se pudo abrir el archivo %s\n", archivoBit);
  543. return -1;
  544. }
  545.  
  546. bytes = fwrite (bitArray, sizeof(dword), NUM_DWORDS, f);
  547.  
  548. if (bytes != NUM_DWORDS)
  549. {
  550. freopen (archivoBit, "wb", f); // Poner tamaño a 0 bytes
  551. fclose (f);
  552.  
  553. printf ("\nNo se pudo guardar el archivo %s\n", archivoBit);
  554. printf ("Se necesitan %s bytes libres en el disco.\n",
  555. str (sizeof(bitArray)));
  556. return -2;
  557. }
  558.  
  559. fclose (f);
  560.  
  561. printf ("\nSe guardó el archivo %s de %s bytes\n",
  562. archivoBit, str (sizeof(dword) * NUM_DWORDS));
  563.  
  564. return 0;
  565. }
  566.  
  567. /**
  568.  * Recupera el vector que indica los primos
  569.  * del disco duro.
  570.  *
  571.  * Si no lo puede recuperar, entonces calcula el
  572.  * vector que indica los primos y después lo guarda
  573.  * en el disco duro.
  574.  */
  575. int RecuperarArchivoPrimos ()
  576. {
  577. FILE *f;
  578. size_t bytes;
  579.  
  580. f = fopen (archivoBit, "rb");
  581.  
  582. if (f == NULL)
  583. {
  584. CalcularPrimosMetodo3 (); // Calcula los primos
  585. GuardarArchivoPrimos (); // y los almacena.
  586. return 1;
  587. }
  588.  
  589. bytes = fread (bitArray, sizeof(dword), NUM_DWORDS, f);
  590.  
  591. if (bytes != NUM_DWORDS)
  592. {
  593. fclose (f);
  594. printf ("\nEl archivo %s está incompleto.\n", archivoBit);
  595.  
  596. CalcularPrimosMetodo3 ();
  597. GuardarArchivoPrimos ();
  598. return 2;
  599. }
  600.  
  601. fclose (f);
  602.  
  603. printf ("\nSe recuperó el archivo %s\n", archivoBit);
  604. return 0;
  605.  
  606. }
  607.  
  608. /**
  609.  * Guarda el vector que indica los primos
  610.  * en el disco duro de forma comprimida.
  611.  *
  612.  * Si son 100.000.000 de números
  613.  * el archivo ocupa 5.761.458 bytes,
  614.  * en vez de 12.500.000 bytes
  615.  * Comprime un 46%
  616.  *
  617.  * Cada byte del archivo indica
  618.  * el número de bits 1 (número de no-primo)
  619.  * consecutivos y un bit 0 (número primo)
  620.  *
  621.  * Se considera que nunca hay más de 255 unos
  622.  * (o números no-primos) seguidos.
  623.  * Sobre 100.000.000 de números parece que se
  624.  * cumple. Hay como máximo 219 unos seguidos.
  625.  *
  626.  * Mejora posible al programa:
  627.  * Ya que el número de no-primos seguidos N,
  628.  * siempre es un número impar (exceptuando
  629.  * los dos primeros), se podría guardar X
  630.  * en vez de N según la fórmula:
  631.  * X=(N-1)/2 o X=(--N)>>1
  632.  * Para descomprimir:
  633.  * N=X*2+1 o N=(N<<1)+1
  634.  * Si X=255 entonces N=511.
  635.  *
  636.  * Ejemplo sobre los primeros 32 bits
  637.  * del array de primos (bit 0 = primo)
  638.  *
  639.  * pos bit comprimido(byte)
  640.  * 0 1
  641.  * 1 1
  642.  * 2 0 2
  643.  * 3 0 0
  644.  * 4 1
  645.  * 5 0 1
  646.  * 6 1
  647.  * 7 0 1
  648.  * 8 1
  649.  * 9 1
  650.  * 10 1
  651.  * 11 0 3
  652.  * 12 1
  653.  * 13 0 1
  654.  * 14 1
  655.  * 15 1
  656.  * 16 1
  657.  * 17 0 3
  658.  * 18 1
  659.  * 19 0 1
  660.  * 20 1
  661.  * 21 1
  662.  * 22 1
  663.  * 23 0 3
  664.  * 24 1
  665.  * 25 1
  666.  * 26 1
  667.  * 27 1
  668.  * 28 1
  669.  * 29 0 5
  670.  * 30 1
  671.  * 31 0 1
  672.  */
  673. int ComprimirArchivoPrimos ()
  674. {
  675. // Variables de cálculo
  676. FILE *f; // el archivo
  677. dword i; // índice
  678. dword item; // un elemento del vector
  679. dword bit; // un bit ordinal (debe ser tipo dword)
  680. int countOnes=0; // cuenta número de no-primos seguidos
  681. dword numBit=0; // número de bit del vector de bits
  682.  
  683. // Variables de información
  684. dword totBytes=0;
  685.  
  686. f = fopen (archivo110, "wb");
  687.  
  688. if (f == NULL)
  689. {
  690. printf ("\nNo se pudo abrir el archivo %s\n", archivo110);
  691. return 1;
  692. }
  693.  
  694. printf ("\nComprimiendo el archivo %s ", archivo110);
  695.  
  696. for (i=0; i<NUM_DWORDS; ++i)
  697. {
  698. item = bitArray[i];
  699.  
  700. for (bit=1; bit; bit<<=1) // Por cada 1 de los 32 bits...
  701. {
  702. if (numBit++ == NUM_BITS) // Si ya no va más...
  703. {
  704. i = NUM_DWORDS; // Salir de los 2 for
  705. break;
  706. }
  707.  
  708. if (item & bit) // Si es no-primo...
  709. {
  710. ++countOnes;
  711.  
  712. if (countOnes == 0) // Control de desbordamiento
  713. {
  714. freopen (archivo110, "wb", f); // Poner tamaño a 0 bytes
  715. fclose (f);
  716.  
  717. printf ("\nNo se puede crear el archivo %s\n", archivo110);
  718. printf ("porque hay más de 255 números no-primos seguidos.\n");
  719. return -1;
  720. }
  721. }
  722. else // Si es primo...
  723. {
  724. fputc (countOnes, f); ++totBytes;
  725. countOnes = 0;
  726.  
  727. ElTiempoNoPasaEnBalde ();
  728. }
  729. }
  730. }
  731. fputc (countOnes, f); ++totBytes; // Las sobras
  732.  
  733. printf ("\nSe creó el archivo %s de %s bytes\n",
  734. archivo110, str (totBytes));
  735.  
  736. fclose (f);
  737. return 0;
  738. }
  739.  
  740. /**
  741.  * Recupera el vector que indica los primos
  742.  * de un archivo comprimido.
  743.  *
  744.  * Si no lo puede recuperar, entonces calcula el
  745.  * vector que indica los primos y después lo guarda
  746.  * en el disco duro.
  747.  */
  748. int DescomprimirArchivoPrimos ()
  749. {
  750. FILE *f; // el archivo
  751. int i; // índice
  752. int countOnes; // cardinal de no-primos seguidos
  753. dword numBit=0; // número de bit del vector de bits
  754.  
  755. #if 0
  756. char buffer[65536];
  757. int numBytes=0;
  758. int index=0;
  759. #endif
  760.  
  761. f = fopen (archivo110, "rb");
  762.  
  763. if (f == NULL)
  764. {
  765. //printf ("No se recuperó el archivo %s\n\n", archivoPrimos);
  766. CalcularPrimosMetodo3 (); // Calcula los primos
  767. ComprimirArchivoPrimos (); // y los almacena.
  768. return 1;
  769. }
  770.  
  771. printf ("\nDescomprimiendo el archivo %s ", archivo110);
  772.  
  773. /* Se sigue una estrategia de marcar números primos
  774.   * porque hay muchos menos que números no-primos
  775.   */
  776.  
  777. for (i=0; i<NUM_DWORDS; ++i)
  778. {
  779. bitArray [i] = 0xFFFFFFFF; // Poner todo a uno (ningún primo)
  780. }
  781.  
  782. #if 1
  783. while ((countOnes = fgetc(f)) != EOF) // Obtener un byte del archivo
  784. {
  785. #else
  786. for (;;)
  787. {
  788. if (index >= numBytes)
  789. {
  790. index = 0;
  791. numBytes = fread (&buffer, sizeof(char), 1, f);
  792. if (numBytes <= 0) break;
  793. }
  794. countOnes = buffer[index++];
  795. #endif
  796.  
  797. for (i=0; i<countOnes; ++i) // Saltarnos unos cuantos bits
  798. {
  799. ++numBit;
  800. }
  801.  
  802. if (numBit >= NUM_BITS) // Si no va más...
  803. {
  804. break; // Se acabó
  805. }
  806.  
  807. CLEAR_BIT(numBit); // Marcar el primo
  808.  
  809. ++numBit; // ­No incluir dentro de la macro anterior!
  810.  
  811. ElTiempoNoPasaEnBalde ();
  812. }
  813.  
  814. fclose (f);
  815.  
  816. //printf ("\nSe recuperó la información de %s\n\n", archivo110);
  817. printf ("\n\n");
  818. return 0;
  819. }
  820.  
  821. //-----------------------------------------------
  822. // CALCULAR PRIMOS SI HACE FALTA
  823.  
  824. typedef enum {MEMORIA, ARCHIVO, COMPRIMIDO, } FormaCalculo;
  825.  
  826. /**
  827.  * Calcula los primos una vez y después
  828.  * ya no los vuelve a calcular más.
  829.  */
  830. void CalcularPrimosDesde (FormaCalculo forma)
  831. {
  832. static bool calculado = false;
  833.  
  834. if (calculado == false)
  835. {
  836. switch (forma)
  837. {
  838. case MEMORIA: CalcularPrimosMetodo3 (); break;
  839. case ARCHIVO: RecuperarArchivoPrimos (); break;
  840. case COMPRIMIDO: DescomprimirArchivoPrimos (); break;
  841. }
  842. calculado = true;
  843. }
  844. }
  845.  
  846. //-----------------------------------------------
  847. // BUSCAR PRIMOS
  848.  
  849.  
  850. /**
  851.  * Indica si es primo
  852.  */
  853. bool EsPrimo (dword numero)
  854. {
  855. if (numero == 0 || numero >= NUM_BITS)
  856. {
  857. return false;
  858. }
  859. else
  860. {
  861. return !TEST_BIT(numero);
  862. }
  863. }
  864.  
  865. /**
  866.  * Indica el número de primo que es
  867.  * el primo indicado
  868.  */
  869. dword OrdinalDelPrimo (dword primo)
  870. {
  871. dword num;
  872. dword totPrimos = 0;
  873.  
  874. for (num=1; num<NUM_BITS; ++num)
  875. {
  876. if (!TEST_BIT(num)) // Es primo
  877. {
  878. ++totPrimos;
  879. }
  880. if (num == primo)
  881. {
  882. return totPrimos;
  883. }
  884. }
  885. return 0;
  886. }
  887.  
  888. /**
  889.  * Muestra en pantalla si el número indicado
  890.  * es primo. Si no lo fuese muestra los primos
  891.  * anterior y posterior al número indicado.
  892.  */
  893. void BuscarPrimosCercanos (const dword numero)
  894. {
  895. dword num;
  896. dword primoAnt = 0;
  897. dword primoSig = 0;
  898.  
  899. CalcularPrimosDesde (COMPRIMIDO);
  900.  
  901. for (num=numero; num>0; --num)
  902. {
  903. if (!TEST_BIT(num)) // Es primo
  904. {
  905. primoAnt = num;
  906. break;
  907. }
  908. }
  909. for (num=numero; num<NUM_BITS; ++num)
  910. {
  911. if (!TEST_BIT(num)) // Es primo
  912. {
  913. primoSig = num;
  914. break;
  915. }
  916. }
  917.  
  918. printf ("El número %s", str (numero));
  919.  
  920. if (numero == primoAnt)
  921. {
  922. printf (" es primo. ");
  923. printf ("El ordinal es %s\n", str (OrdinalDelPrimo (numero)));
  924. }
  925. else
  926. {
  927. printf (" tiene como primos cercanos %s",
  928. primoAnt ? str (primoAnt) : "<no disponible>");
  929.  
  930. printf (" y %s\n",
  931. primoSig ? str (primoSig) : "<no disponible>");
  932. }
  933. }
  934.  
  935. /**
  936.  * Muestra en pantalla el número de primo indicado.
  937.  *
  938.  * Ejemplo:
  939.  *
  940.  * El primo 1 es 2
  941.  * El primo 2 es 3
  942.  * El primo 3 es 4
  943.  * El primo 4 es 5
  944.  * El primo 5 es 11
  945.  * El primo 6 es 12
  946.  * El primo 7 es 17
  947.  * El primo 8 es 19
  948.  * ...
  949.  */
  950. void BuscarPrimoNumero (const dword numero)
  951. {
  952. dword num;
  953. dword totPrimos = 0;
  954.  
  955. CalcularPrimosDesde (COMPRIMIDO);
  956.  
  957. for (num=1; num<NUM_BITS; ++num)
  958. {
  959. if (!TEST_BIT(num)) // Es primo
  960. {
  961. ++totPrimos;
  962.  
  963. if (totPrimos == numero)
  964. {
  965. printf("\nEl primo número %s", str (numero));
  966. printf(" es %s\n", str (num));
  967. return;
  968. }
  969. }
  970. }
  971. printf ("\nError: En total hay %s primos calculados.\n", str (totPrimos));
  972. }
  973.  
  974. /**
  975.  * Buscar primos entre los números indicados
  976.  */
  977. void BuscarPrimosEntre (dword min, dword max)
  978. {
  979. dword num;
  980. dword totPrimos=0;
  981.  
  982. CalcularPrimosDesde (COMPRIMIDO);
  983.  
  984. if (min > max) swap (&min, &max);
  985.  
  986. printf ("Primos entre %s", str (min));
  987. printf (" y %s\n\n", str (max));
  988.  
  989. for (num=min; num<=max; ++num)
  990. {
  991. if (!TEST_BIT(num)) // Es primo
  992. {
  993. ++totPrimos;
  994. //printf ("%10u", num);
  995. printf ("%13s", str (num));
  996. if ((totPrimos % 6) == 0) printf ("\n");
  997. }
  998. }
  999. printf ("\n\nEn total hay %s primos\n",
  1000. str (totPrimos));
  1001. }
  1002.  
  1003. /**
  1004.  * Descompone el número indicado en sus
  1005.  * factores primos
  1006.  */
  1007. void DescomponerNumero (dword numero)
  1008. {
  1009. dword num;
  1010. dword potencia;
  1011.  
  1012. CalcularPrimosDesde (COMPRIMIDO);
  1013.  
  1014. printf ("Factores primos de %s = ",
  1015. str (numero));
  1016.  
  1017. for (num=2; num <= numero; ++num)
  1018. {
  1019. if (!TEST_BIT(num)) // Es primo
  1020. {
  1021. potencia = 0;
  1022.  
  1023. for (;;)
  1024. {
  1025. dword cociente = numero / num;
  1026. dword resto = numero % num;
  1027.  
  1028. if (resto != 0)
  1029. {
  1030. break;
  1031. }
  1032. else
  1033. {
  1034. numero = cociente;
  1035. ++potencia;
  1036. }
  1037. }
  1038.  
  1039. if (potencia)
  1040. {
  1041. printf ("%s", str (num));
  1042. if (potencia != 1) printf ("^%lu", potencia);
  1043. printf (" * ");
  1044. }
  1045. }
  1046. }
  1047. printf ("\b\b \n");
  1048. }
  1049.  
  1050.  
  1051. //-----------------------------------------------
  1052. // CONTAR 1 Y 0 SEGUIDOS
  1053.  
  1054. /**
  1055.  * Muestra en pantalla
  1056.  * el número de 1 (no-primos) consecutivos y
  1057.  * el número de 0 (primos) consecutivos
  1058.  *
  1059.  * Sobre 100.000.000 hay 2 primos consecutivos
  1060.  * y 219 no-primos consecutivos.
  1061.  *
  1062.  */
  1063. void ContarUnosCerosConsecutivos ()
  1064. {
  1065. dword num;
  1066. dword numUnos=0;
  1067. dword numCeros=0;
  1068. dword cuenta;
  1069. int bit, ultimo;
  1070.  
  1071. CalcularPrimosDesde (COMPRIMIDO);
  1072.  
  1073. ultimo = 1;
  1074. cuenta = 1;
  1075.  
  1076. for (num=1; num<NUM_BITS; ++num)
  1077. {
  1078. bit = TEST_BIT(num) ? 1 : 0;
  1079.  
  1080. if (bit != ultimo)
  1081. {
  1082. if (ultimo == 0 && cuenta > numCeros) numCeros = cuenta; else
  1083. if (ultimo == 1 && cuenta > numUnos) numUnos = cuenta;
  1084. cuenta = 0;
  1085. ultimo = bit;
  1086. }
  1087. ++cuenta;
  1088. }
  1089.  
  1090. printf ("La cantidad máxima de PRIMOS consecutivos es %lu\n", numCeros);
  1091. printf ("La cantidad máxima de NO-PRIMOS consecutivos es %lu\n", numUnos);
  1092. }
  1093.  
  1094.  
  1095. //-----------------------------------------------
  1096. // CONVETIR TEXTO EN NUMERO
  1097.  
  1098. dword SumaASCII (char *texto)
  1099. {
  1100. dword suma=0;
  1101. char *s;
  1102.  
  1103. for (s=texto; *s; ++s)
  1104. {
  1105. suma += *s;
  1106. }
  1107.  
  1108. return suma;
  1109. }
  1110.  
  1111. char letras [] =
  1112. {
  1113. 'a', 'b', 'c', 'd', 'e',
  1114. 'f', 'g', 'h', 'i', 'j',
  1115. 'k', 'l', 'm', 'n', '~',
  1116. 'o', 'p', 'q', 'r', 's',
  1117. 't', 'u', 'v', 'w', 'x',
  1118. 'y', 'z',
  1119. };
  1120.  
  1121. dword SumaLetras (char *texto)
  1122. {
  1123. dword suma=0;
  1124. char *s;
  1125. int i;
  1126. char c;
  1127.  
  1128. for (s=texto; *s; ++s)
  1129. {
  1130. c = tolower (*s);
  1131.  
  1132. for (i=0; i<ARRAY_SIZE(letras); ++i)
  1133. {
  1134. if (c == letras[i])
  1135. {
  1136. suma += (i + 1);
  1137. break;
  1138. }
  1139. }
  1140. }
  1141. return suma;
  1142. }
  1143.  
  1144. /**
  1145.  * Busca si hay algún primo en el texto
  1146.  */
  1147. void BuscarPrimoEnTexto (char *texto)
  1148. {
  1149. dword suma1 = SumaASCII (texto);
  1150. dword suma2 = SumaLetras (texto);
  1151.  
  1152. CalcularPrimosDesde (COMPRIMIDO);
  1153.  
  1154. printf ("%s\n", texto);
  1155.  
  1156. printf ("ÃSuma ASCII = %s %s\n", str (suma1),
  1157. EsPrimo(suma1)? "es primo":"");
  1158.  
  1159. printf ("ÀSuma letras = %s %s\n", str (suma2),
  1160. EsPrimo(suma2)? "es primo":"");
  1161. }
  1162.  
  1163. /**
  1164.  * Busca primo en archivo
  1165.  */
  1166. void BuscarPrimoEnArchivo (char *filename)
  1167. {
  1168. FILE *f;
  1169. int car;
  1170. dword suma=0;
  1171. dword cuenta=0;
  1172.  
  1173. f = fopen (filename, "rb");
  1174.  
  1175. CalcularPrimosDesde (COMPRIMIDO);
  1176.  
  1177. if (f == NULL)
  1178. {
  1179. BuscarPrimoEnTexto (filename);
  1180. return;
  1181. }
  1182.  
  1183. while ((car = fgetc(f)) != EOF)
  1184. {
  1185. ++cuenta;
  1186.  
  1187. if ((0xFFFFFFFF - car) >= suma)
  1188. {
  1189. suma += car;
  1190. }
  1191. else
  1192. {
  1193. fclose (f);
  1194. printf ("Desbordamiento al sumar los bytes del archivo %s\n", filename);
  1195. return;
  1196. }
  1197. }
  1198.  
  1199. fclose (f);
  1200.  
  1201. //printf ("Tamaño: %13s %s ", str(cuenta), EsPrimo(cuenta)? "es primo":" ");
  1202. printf ("%s %13s suma ", EsPrimo(suma)? "Es primo":" ", str(suma));
  1203. printf ("\"%s\"", filename);
  1204. }
  1205.  
  1206. //-----------------------------------------------
  1207. // AYUDA
  1208.  
  1209. /**
  1210.  * Muestra en pantalla la forma en que
  1211.  * se utiliza este programa.
  1212.  */
  1213. void MostrarAyuda ()
  1214. {
  1215. puts (
  1216. "PRIMOS, FJCR (f) junio-1999 v0.2\n"
  1217. "Sintaxis: primos argumentos números ...\n"
  1218. "\n"
  1219. "Argumentos:\n"
  1220. " A-B primos entre A y B\n"
  1221. " -p N primos cercanos a N\n"
  1222. " -n N primo número N\n"
  1223. " -f N descomponer en factores primos\n"
  1224. "Otros:\n"
  1225. " -m calcular en memoria (sin archivo)\n"
  1226. " -c crear el archivo comprimido de primos .110\n"
  1227. " -1 máx. número no-primos consecutivos\n"
  1228. " -g guardar primos en el archivo .bit\n"
  1229. " -r recuperar primos del archivo .bit\n"
  1230. "\n"
  1231. "Ejemplos:\n"
  1232. " primos 13 1.355 -n 65 ...\n"
  1233. " primos * \"Cualquier texto\"\n"
  1234. "\n"
  1235. "Eratóstenes.- Célebre matemático griego. Nació\n"
  1236. "alrededor del 276 a.C. y murió el año 184 a.C.\n"
  1237. "Calculó la circunferencia de la Tierra y elaboró\n"
  1238. "un método para determinar los números primos.\n"
  1239. );
  1240. }
  1241.  
  1242.  
  1243. //-----------------------------------------------
  1244. // PROCESAR ARGUMENTOS
  1245.  
  1246. /**
  1247.  * Procesa los argumentos en línea de comandos.
  1248.  */
  1249. int ProcesarArgumentos (int numArgs, char *args[])
  1250. {
  1251. int i;
  1252. dword num;
  1253. enum {PRIMO, NUMERO, FACTORES} tipo = PRIMO;
  1254. char c;
  1255.  
  1256. for (i=1; i<numArgs; ++i)
  1257. {
  1258. c = args[i][0];
  1259.  
  1260. if (c == '-' || c == '/')
  1261. {
  1262. switch (toupper (args[i][1]))
  1263. {
  1264. case 'M': CalcularPrimosDesde (MEMORIA); break;
  1265.  
  1266. case 'C': CalcularPrimosDesde (MEMORIA);
  1267. ComprimirArchivoPrimos (); break;
  1268.  
  1269. case 'G': CalcularPrimosDesde (MEMORIA);
  1270. GuardarArchivoPrimos (); break;
  1271. case 'R': CalcularPrimosDesde (ARCHIVO); break;
  1272.  
  1273. case '0':
  1274. case '1': ContarUnosCerosConsecutivos (); break;
  1275.  
  1276. case 'P': tipo = PRIMO; break;
  1277. case 'N': tipo = NUMERO; break;
  1278. case 'F': tipo = FACTORES; break;
  1279.  
  1280. default: printf ("%s es un parámetro erróneo.\n", args[i]);
  1281. }
  1282. }
  1283. else if (isdigit (c)) // c >= '0' && c <= '9'
  1284. {
  1285. char *s = strstr (args[i], "-");
  1286.  
  1287. if (s != NULL) // Rango de números
  1288. {
  1289. dword num1 = dw (args[i]); // strtoul (args[i], NULL, 0);
  1290. dword num2 = dw (++s); // strtoul (++s, NULL, 0);
  1291.  
  1292. if (num1 == 0 || num1 >= NUM_BITS
  1293. || num2 == 0 || num2 >= NUM_BITS)
  1294. {
  1295. printf ("%s no es válido en el ", args[i]);
  1296. printf ("rango entre 1 y %s\n", str (NUM_BITS-1));
  1297. }
  1298. else
  1299. {
  1300. switch (tipo)
  1301. {
  1302. case PRIMO:
  1303. BuscarPrimosEntre (num1, num2);
  1304. break;
  1305. case NUMERO:
  1306. for (num=num1; num<=num2; ++num)
  1307. BuscarPrimoNumero (num);
  1308. break;
  1309. case FACTORES:
  1310. for (num=num1; num<=num2; ++num)
  1311. DescomponerNumero (num);
  1312. break;
  1313. }
  1314. }
  1315. }
  1316. else // Un número
  1317. {
  1318. dword num = dw (args[i]); // strtoul (args[i], NULL, 0);
  1319.  
  1320. if (num == 0 || num >= NUM_BITS)
  1321. {
  1322. printf ("%s está fuera del ", args[i]);
  1323. printf ("rango entre 1 y %s\n", str (NUM_BITS-1));
  1324. }
  1325. else
  1326. {
  1327. switch (tipo)
  1328. {
  1329. case PRIMO: BuscarPrimosCercanos (num); break;
  1330. case NUMERO: BuscarPrimoNumero (num); break;
  1331. case FACTORES: DescomponerNumero (num); break;
  1332. }
  1333. }
  1334. }
  1335. }
  1336. else
  1337. {
  1338. //BuscarPrimoEnTexto (args[i]);
  1339. BuscarPrimoEnArchivo (args[i]);
  1340. }
  1341.  
  1342. printf ("\n");
  1343. }
  1344. return 0;
  1345. }
  1346.  
  1347.  
  1348. //-----------------------------------------------
  1349. // PRINCIPAL
  1350.  
  1351. int main (int numArgs, char *args[])
  1352. {
  1353.  
  1354. #ifdef METODO1
  1355. CalcularPrimosMetodo1 ();
  1356. #endif
  1357.  
  1358. #ifdef METODO2
  1359. CalcularPrimosMetodo2 ();
  1360. #endif
  1361.  
  1362. #ifdef METODO3
  1363. if (numArgs > 1)
  1364. {
  1365. ProcesarArgumentos (numArgs, args);
  1366.  
  1367. // PRUEBAS:
  1368. //ContarUnosCerosConsecutivos ();
  1369. //CalcularPrimosMetodo3 ();
  1370. //ComprimirArchivoPrimos ();
  1371. //DescomprimirArchivoPrimos ();
  1372. //GuardarArchivoPrimos ();
  1373. }
  1374. else
  1375. {
  1376. MostrarAyuda ();
  1377. }
  1378. #endif
  1379.  
  1380. return 0;
  1381. }
  1382.  
  1383. // END OF FILE
  1384.  

Proinf.net