primos.c

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

Proinf.net