Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - ottimizzare il codice? scomposizione in fattori primi
Forum - C/C++ - ottimizzare il codice? scomposizione in fattori primi - Pagina 2

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 21:00
Giovedì, 05/01/2017
Infatti lo "ingrandisci" nel senso che lo crei, lo riempi, ne crei uno nuovo più grande e lo sostituisci con quello di partenza dopo averlo copiato.....

P.S. i vostri programmi sono più output che funzionalità.... Rimuovete tutto quell'output inutile e l'input prendetelo da char** argv

Da un generico programma io mi aspetto di poterlo eseguire così:

scomponi 128

e in output mi darà
2*2*2*2*....... (*1)

oppure:

scomponi 0

e in output avrò: "Lo 0 non e' scomponibile"

Aggiungere menu significa rompere la comodità del tasto "freccia su" delle console su linux, pulire lo schermo significa perdere la storia delle operazioni (che è sempre gestita dalla console su linux).
Sinceramente un generico menu fatto in quel modo renderebbe un programma assolutamente NON pratico e io eviterei a tutti i costi l'ultilizzo.......
ed anche la lettura del sorgente, visto che è al 80% input e output per menu e attesa di un buon input.


Ah io renderei il metodo per la scomposizione ricorsivo :)

Codice sorgente - presumibilmente C++
  1. void scomponi(int num, std::vector<int> *divisori) {
  2.     if (num == 1) {
  3.          return;
  4.     } else {
  5.          //cerco un divisore, fra i numeri primi minori di num e lo chiamo div (nei divisori NON deve essere presente l'1 per ovvii motivi)
  6.          divisori->push_back(div);
  7.          return scomponi(num / div);
  8.     }
  9. }

Ultima modifica effettuata da TheDarkJuster il 05/01/2017 alle 21:12
PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 700
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 21:20
Giovedì, 05/01/2017
Prendendo spunto dal suggerimento di TheDarkJuster (usare una tabella di numeri primi precalcolati), ho modificato il file main.c:

File main.c

Codice sorgente - presumibilmente C++
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include "tabella_numeri_primi_65535.h"
  4. #include "interfaccia.h"
  5.  
  6. // ===> MACRO/COSTANTI/STRINGHE <===============================================
  7.  
  8. #define MAX_FATTORI 36 // in effetti, unsigned long puo' contenere un valore
  9.                        // massimo di 2^32-1, per cui nella scomposizione non
  10.                        // ci possono essere piu' di 32 fattori primi
  11.  
  12. const char *kStrPres[] = {
  13. "SCOMPOSIZIONE IN FATTORI PRIMI",
  14. "questo programma scompone in fattori primi valori interi compresi",
  15. "tra 2 e 4294967295, presentando il risultato sia in forma di",
  16. "calcolo in colonna, sia come formula riassuntiva in linea"
  17. };
  18.  
  19. const int kNStrPres = sizeof(kStrPres)/sizeof(*kStrPres);
  20.  
  21. // ===> PROTOTIPI DI FUNZIONI <=================================================
  22.  
  23. int scomponi( unsigned long n, unsigned long *fattori );
  24.  
  25. // ===> FUNZIONE D'ACCESSO AL PROGRAMMA <=======================================
  26.  
  27. int main() {
  28.     unsigned long n, fattori[MAX_FATTORI];
  29.  
  30.     presenta_in_console( kStrPres, kNStrPres );
  31.  
  32.     do {
  33.         memset( fattori, 0, sizeof(*fattori)*MAX_FATTORI );
  34.  
  35.         n = chiedi_numero_da_scomporre();
  36.  
  37.         if( scomponi(n,fattori) == 0 ) {
  38.             scrivi_tabella_scomposizione( n, fattori );
  39.             scrivi_scomposizione_in_linea( n, fattori );
  40.         }
  41.     } while( chiedi_se_continuare() );
  42.  
  43.     return 0;
  44. }
  45.  
  46. // ===> FUNZIONE DI SCOMPOSIZIONE IN FATTORI PRIMI <============================
  47.  
  48. int scomponi( unsigned long n, unsigned long *fattori ) {
  49.     if( n > 1 ) {
  50.         int i_np = 0; // i_np = indice del numero primo
  51.         int i_ft = 0; // i_ft = indice del fattore
  52.         unsigned long dc = kTabNp[i_np]; // dc = divisore corrente
  53.  
  54.         while( n!=1 ) {
  55.             if( n%dc ) {
  56.                 dc = kTabNp[++i_np];
  57.             }
  58.             else {
  59.                 fattori[i_ft++] = dc;
  60.                 n /= dc;
  61.             }
  62.         }
  63.  
  64.         return 0;
  65.     }
  66.     else {
  67.         if( n == 0 )
  68.             mostra_errore_in_console( "lo zero non e' scomponibile" );
  69.         else mostra_errore_in_console( "l'unita' non e' scomponibile" );
  70.  
  71.         return 1;
  72.     }
  73. }


Ovviamente ho dovuto anche aggiungere un file di intestazione dove compare la tabella dei numeri primi:

File tabella_numeri_primi_65535.h

Codice sorgente - presumibilmente C++
  1. #ifndef TABELLA_NUMERI_PRIMI_65535_H_INCLUDED
  2. #define TABELLA_NUMERI_PRIMI_65535_H_INCLUDED
  3.  
  4. const unsigned short kTabNp[] = {
  5.     2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
  6.     31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  7.     73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
  8.     127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  9.     179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  10.     233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
  11.     283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
  12.     353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
  13.     419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
  14.     467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
  15.     547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
  16.     607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
  17.     661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  18.     739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
  19.     811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
  20.     877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
  21.     947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
  22.     1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
  23.     1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
  24.     1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
  25.     1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
  26.     1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
  27.     1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
  28.     1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
  29.     1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
  30.     1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
  31.     1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
  32.     1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
  33.     1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
  34.     1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
  35.     1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
  36.     2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
  37.     2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
  38.     2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
  39.     2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
  40.     2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
  41.     2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
  42.     2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
  43.     2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
  44.     2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
  45.     2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
  46.     2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
  47.     2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
  48.     3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
  49.     3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
  50.     3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
  51.     3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
  52.     3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
  53.     3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
  54.     3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
  55.     3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
  56.     3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
  57.     3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
  58.     3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
  59.     3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
  60.     4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
  61.     4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
  62.     4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
  63.     4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
  64.     4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
  65.     4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
  66.     4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
  67.     4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
  68.     4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
  69.     4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831,
  70.     4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
  71.     4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003,
  72.     5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
  73.     5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179,
  74.     5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279,
  75.     5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387,
  76.     5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
  77.     5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
  78.     5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639,
  79.     5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693,
  80.     5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
  81.     5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
  82.     5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
  83.     5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053,
  84.     6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
  85.     6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221,
  86.     6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301,
  87.     6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367,
  88.     6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
  89.     6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571,
  90.     6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
  91.     6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761,
  92.     6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
  93.     6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917,
  94.     6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
  95.     7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
  96.     7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
  97.     7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297,
  98.     7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411,
  99.     7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499,
  100.     7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
  101.     7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643,
  102.     7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723,
  103.     7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
  104.     7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
  105.     7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017,
  106.     8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111,
  107.     8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219,
  108.     8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
  109.     8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387,
  110.     8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501,
  111.     8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597,
  112.     8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
  113.     8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741,
  114.     8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831,
  115.     8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929,
  116.     8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
  117.     9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109,
  118.     9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199,
  119.     9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283,
  120.     9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
  121.     9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439,
  122.     9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533,
  123.     9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631,
  124.     9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
  125.     9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811,
  126.     9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887,
  127.     9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007,
  128.     10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
  129.     10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177,
  130.     10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271,
  131.     10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343,
  132.     10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
  133.     10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567,
  134.     10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657,
  135.     10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739,
  136.     10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
  137.     10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949,
  138.     10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059,
  139.     11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149,
  140.     11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
  141.     11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329,
  142.     11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443,
  143.     11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527,
  144.     11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
  145.     11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777,
  146.     11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833,
  147.     11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933,
  148.     11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
  149.     12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109,
  150.     12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211,
  151.     12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289,
  152.     12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
  153.     12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487,
  154.     12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553,
  155.     12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641,
  156.     12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
  157.     12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829,
  158.     12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923,
  159.     12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007,
  160.     13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
  161.     13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187,
  162.     13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309,
  163.     13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411,
  164.     13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
  165.     13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619,
  166.     13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697,
  167.     13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781,
  168.     13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
  169.     13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967,
  170.     13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081,
  171.     14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197,
  172.     14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
  173.     14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419,
  174.     14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519,
  175.     14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593,
  176.     14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
  177.     14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767,
  178.     14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851,
  179.     14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947,
  180.     14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
  181.     15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149,
  182.     15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259,
  183.     15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319,
  184.     15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
  185.     15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497,
  186.     15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607,
  187.     15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679,
  188.     15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
  189.     15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881,
  190.     15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971,
  191.     15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069,
  192.     16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
  193.     16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267,
  194.     16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381,
  195.     16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481,
  196.     16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
  197.     16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691,
  198.     16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811,
  199.     16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903,
  200.     16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
  201.     17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093,
  202.     17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191,
  203.     17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317,
  204.     17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
  205.     17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471, 17477,
  206.     17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569, 17573,
  207.     17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669,
  208.     17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
  209.     17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891,
  210.     17903, 17909, 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971,
  211.     17977, 17981, 17987, 17989, 18013, 18041, 18043, 18047, 18049, 18059,
  212.     18061, 18077, 18089, 18097, 18119, 18121, 18127, 18131, 18133, 18143,
  213.     18149, 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229, 18233,
  214.     18251, 18253, 18257, 18269, 18287, 18289, 18301, 18307, 18311, 18313,
  215.     18329, 18341, 18353, 18367, 18371, 18379, 18397, 18401, 18413, 18427,
  216.     18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493, 18503, 18517,
  217.     18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617, 18637,
  218.     18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749,
  219.     18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899,
  220.     18911, 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009,
  221.     19013, 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121,
  222.     19139, 19141, 19157, 19163, 19181, 19183, 19207, 19211, 19213, 19219,
  223.     19231, 19237, 19249, 19259, 19267, 19273, 19289, 19301, 19309, 19319,
  224.     19333, 19373, 19379, 19381, 19387, 19391, 19403, 19417, 19421, 19423,
  225.     19427, 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471, 19477,
  226.     19483, 19489, 19501, 19507, 19531, 19541, 19543, 19553, 19559, 19571,
  227.     19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687, 19697, 19699,
  228.     19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777, 19793,
  229.     19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891,
  230.     19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991,
  231.     19993, 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071,
  232.     20089, 20101, 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149,
  233.     20161, 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249, 20261,
  234.     20269, 20287, 20297, 20323, 20327, 20333, 20341, 20347, 20353, 20357,
  235.     20359, 20369, 20389, 20393, 20399, 20407, 20411, 20431, 20441, 20443,
  236.     20477, 20479, 20483, 20507, 20509, 20521, 20533, 20543, 20549, 20551,
  237.     20563, 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681, 20693,
  238.     20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753, 20759, 20771,
  239.     20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887, 20897,
  240.     20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983,
  241.     21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067,
  242.     21089, 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169,
  243.     21179, 21187, 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277,
  244.     21283, 21313, 21317, 21319, 21323, 21341, 21347, 21377, 21379, 21383,
  245.     21391, 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487, 21491,
  246.     21493, 21499, 21503, 21517, 21521, 21523, 21529, 21557, 21559, 21563,
  247.     21569, 21577, 21587, 21589, 21599, 21601, 21611, 21613, 21617, 21647,
  248.     21649, 21661, 21673, 21683, 21701, 21713, 21727, 21737, 21739, 21751,
  249.     21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839, 21841,
  250.     21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937, 21943,
  251.     21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039,
  252.     22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123,
  253.     22129, 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229,
  254.     22247, 22259, 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307,
  255.     22343, 22349, 22367, 22369, 22381, 22391, 22397, 22409, 22433, 22441,
  256.     22447, 22453, 22469, 22481, 22483, 22501, 22511, 22531, 22541, 22543,
  257.     22549, 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639, 22643,
  258.     22651, 22669, 22679, 22691, 22697, 22699, 22709, 22717, 22721, 22727,
  259.     22739, 22741, 22751, 22769, 22777, 22783, 22787, 22807, 22811, 22817,
  260.     22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921, 22937, 22943,
  261.     22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027, 23029,
  262.     23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099,
  263.     23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203,
  264.     23209, 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321,
  265.     23327, 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447,
  266.     23459, 23473, 23497, 23509, 23531, 23537, 23539, 23549, 23557, 23561,
  267.     23563, 23567, 23581, 23593, 23599, 23603, 23609, 23623, 23627, 23629,
  268.     23633, 23663, 23669, 23671, 23677, 23687, 23689, 23719, 23741, 23743,
  269.     23747, 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819, 23827,
  270.     23831, 23833, 23857, 23869, 23873, 23879, 23887, 23893, 23899, 23909,
  271.     23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993, 24001, 24007,
  272.     24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083, 24091,
  273.     24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169,
  274.     24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281,
  275.     24317, 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413,
  276.     24419, 24421, 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517,
  277.     24527, 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631, 24659,
  278.     24671, 24677, 24683, 24691, 24697, 24709, 24733, 24749, 24763, 24767,
  279.     24781, 24793, 24799, 24809, 24821, 24841, 24847, 24851, 24859, 24877,
  280.     24889, 24907, 24917, 24919, 24923, 24943, 24953, 24967, 24971, 24977,
  281.     24979, 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087, 25097,
  282.     25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169, 25171, 25183,
  283.     25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301, 25303,
  284.     25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391,
  285.     25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471,
  286.     25523, 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603,
  287.     25609, 25621, 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693,
  288.     25703, 25717, 25733, 25741, 25747, 25759, 25763, 25771, 25793, 25799,
  289.     25801, 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903, 25913,
  290.     25919, 25931, 25933, 25939, 25943, 25951, 25969, 25981, 25997, 25999,
  291.     26003, 26017, 26021, 26029, 26041, 26053, 26083, 26099, 26107, 26111,
  292.     26113, 26119, 26141, 26153, 26161, 26171, 26177, 26183, 26189, 26203,
  293.     26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293, 26297,
  294.     26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393, 26399,
  295.     26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497,
  296.     26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633,
  297.     26641, 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711,
  298.     26713, 26717, 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801,
  299.     26813, 26821, 26833, 26839, 26849, 26861, 26863, 26879, 26881, 26891,
  300.     26893, 26903, 26921, 26927, 26947, 26951, 26953, 26959, 26981, 26987,
  301.     26993, 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073, 27077,
  302.     27091, 27103, 27107, 27109, 27127, 27143, 27179, 27191, 27197, 27211,
  303.     27239, 27241, 27253, 27259, 27271, 27277, 27281, 27283, 27299, 27329,
  304.     27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431, 27437, 27449,
  305.     27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541, 27551,
  306.     27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691,
  307.     27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767,
  308.     27773, 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827,
  309.     27847, 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947,
  310.     27953, 27961, 27967, 27983, 27997, 28001, 28019, 28027, 28031, 28051,
  311.     28057, 28069, 28081, 28087, 28097, 28099, 28109, 28111, 28123, 28151,
  312.     28163, 28181, 28183, 28201, 28211, 28219, 28229, 28277, 28279, 28283,
  313.     28289, 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393, 28403,
  314.     28409, 28411, 28429, 28433, 28439, 28447, 28463, 28477, 28493, 28499,
  315.     28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571, 28573, 28579,
  316.     28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643, 28649,
  317.     28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729,
  318.     28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837,
  319.     28843, 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933,
  320.     28949, 28961, 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059,
  321.     29063, 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153, 29167,
  322.     29173, 29179, 29191, 29201, 29207, 29209, 29221, 29231, 29243, 29251,
  323.     29269, 29287, 29297, 29303, 29311, 29327, 29333, 29339, 29347, 29363,
  324.     29383, 29387, 29389, 29399, 29401, 29411, 29423, 29429, 29437, 29443,
  325.     29453, 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569, 29573,
  326.     29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663, 29669, 29671,
  327.     29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803, 29819,
  328.     29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921,
  329.     29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059,
  330.     30071, 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137,
  331.     30139, 30161, 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241,
  332.     30253, 30259, 30269, 30271, 30293, 30307, 30313, 30319, 30323, 30341,
  333.     30347, 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467, 30469,
  334.     30491, 30493, 30497, 30509, 30517, 30529, 30539, 30553, 30557, 30559,
  335.     30577, 30593, 30631, 30637, 30643, 30649, 30661, 30671, 30677, 30689,
  336.     30697, 30703, 30707, 30713, 30727, 30757, 30763, 30773, 30781, 30803,
  337.     30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869, 30871,
  338.     30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977, 30983,
  339.     31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091,
  340.     31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183,
  341.     31189, 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259,
  342.     31267, 31271, 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357,
  343.     31379, 31387, 31391, 31393, 31397, 31469, 31477, 31481, 31489, 31511,
  344.     31513, 31517, 31531, 31541, 31543, 31547, 31567, 31573, 31583, 31601,
  345.     31607, 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699, 31721,
  346.     31723, 31727, 31729, 31741, 31751, 31769, 31771, 31793, 31799, 31817,
  347.     31847, 31849, 31859, 31873, 31883, 31891, 31907, 31957, 31963, 31973,
  348.     31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057, 32059, 32063,
  349.     32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143, 32159,
  350.     32173, 32183, 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257,
  351.     32261, 32297, 32299, 32303, 32309, 32321, 32323, 32327, 32341, 32353,
  352.     32359, 32363, 32369, 32371, 32377, 32381, 32401, 32411, 32413, 32423,
  353.     32429, 32441, 32443, 32467, 32479, 32491, 32497, 32503, 32507, 32531,
  354.     32533, 32537, 32561, 32563, 32569, 32573, 32579, 32587, 32603, 32609,
  355.     32611, 32621, 32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717,
  356.     32719, 32749, 32771, 32779, 32783, 32789, 32797, 32801, 32803, 32831,
  357.     32833, 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933, 32939,
  358.     32941, 32957, 32969, 32971, 32983, 32987, 32993, 32999, 33013, 33023,
  359.     33029, 33037, 33049, 33053, 33071, 33073, 33083, 33091, 33107, 33113,
  360.     33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199, 33203, 33211,
  361.     33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331, 33343,
  362.     33347, 33349, 33353, 33359, 33377, 33391, 33403, 33409, 33413, 33427,
  363.     33457, 33461, 33469, 33479, 33487, 33493, 33503, 33521, 33529, 33533,
  364.     33547, 33563, 33569, 33577, 33581, 33587, 33589, 33599, 33601, 33613,
  365.     33617, 33619, 33623, 33629, 33637, 33641, 33647, 33679, 33703, 33713,
  366.     33721, 33739, 33749, 33751, 33757, 33767, 33769, 33773, 33791, 33797,
  367.     33809, 33811, 33827, 33829, 33851, 33857, 33863, 33871, 33889, 33893,
  368.     33911, 33923, 33931, 33937, 33941, 33961, 33967, 33997, 34019, 34031,
  369.     34033, 34039, 34057, 34061, 34123, 34127, 34129, 34141, 34147, 34157,
  370.     34159, 34171, 34183, 34211, 34213, 34217, 34231, 34253, 34259, 34261,
  371.     34267, 34273, 34283, 34297, 34301, 34303, 34313, 34319, 34327, 34337,
  372.     34351, 34361, 34367, 34369, 34381, 34403, 34421, 34429, 34439, 34457,
  373.     34469, 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537,
  374.     34543, 34549, 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649,
  375.     34651, 34667, 34673, 34679, 34687, 34693, 34703, 34721, 34729, 34739,
  376.     34747, 34757, 34759, 34763, 34781, 34807, 34819, 34841, 34843, 34847,
  377.     34849, 34871, 34877, 34883, 34897, 34913, 34919, 34939, 34949, 34961,
  378.     34963, 34981, 35023, 35027, 35051, 35053, 35059, 35069, 35081, 35083,
  379.     35089, 35099, 35107, 35111, 35117, 35129, 35141, 35149, 35153, 35159,
  380.     35171, 35201, 35221, 35227, 35251, 35257, 35267, 35279, 35281, 35291,
  381.     35311, 35317, 35323, 35327, 35339, 35353, 35363, 35381, 35393, 35401,
  382.     35407, 35419, 35423, 35437, 35447, 35449, 35461, 35491, 35507, 35509,
  383.     35521, 35527, 35531, 35533, 35537, 35543, 35569, 35573, 35591, 35593,
  384.     35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747, 35753, 35759,
  385.     35771, 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851, 35863,
  386.     35869, 35879, 35897, 35899, 35911, 35923, 35933, 35951, 35963, 35969,
  387.     35977, 35983, 35993, 35999, 36007, 36011, 36013, 36017, 36037, 36061,
  388.     36067, 36073, 36083, 36097, 36107, 36109, 36131, 36137, 36151, 36161,
  389.     36187, 36191, 36209, 36217, 36229, 36241, 36251, 36263, 36269, 36277,
  390.     36293, 36299, 36307, 36313, 36319, 36341, 36343, 36353, 36373, 36383,
  391.     36389, 36433, 36451, 36457, 36467, 36469, 36473, 36479, 36493, 36497,
  392.     36523, 36527, 36529, 36541, 36551, 36559, 36563, 36571, 36583, 36587,
  393.     36599, 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683, 36691,
  394.     36697, 36709, 36713, 36721, 36739, 36749, 36761, 36767, 36779, 36781,
  395.     36787, 36791, 36793, 36809, 36821, 36833, 36847, 36857, 36871, 36877,
  396.     36887, 36899, 36901, 36913, 36919, 36923, 36929, 36931, 36943, 36947,
  397.     36973, 36979, 36997, 37003, 37013, 37019, 37021, 37039, 37049, 37057,
  398.     37061, 37087, 37097, 37117, 37123, 37139, 37159, 37171, 37181, 37189,
  399.     37199, 37201, 37217, 37223, 37243, 37253, 37273, 37277, 37307, 37309,
  400.     37313, 37321, 37337, 37339, 37357, 37361, 37363, 37369, 37379, 37397,
  401.     37409, 37423, 37441, 37447, 37463, 37483, 37489, 37493, 37501, 37507,
  402.     37511, 37517, 37529, 37537, 37547, 37549, 37561, 37567, 37571, 37573,
  403.     37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649, 37657, 37663,
  404.     37691, 37693, 37699, 37717, 37747, 37781, 37783, 37799, 37811, 37813,
  405.     37831, 37847, 37853, 37861, 37871, 37879, 37889, 37897, 37907, 37951,
  406.     37957, 37963, 37967, 37987, 37991, 37993, 37997, 38011, 38039, 38047,
  407.     38053, 38069, 38083, 38113, 38119, 38149, 38153, 38167, 38177, 38183,
  408.     38189, 38197, 38201, 38219, 38231, 38237, 38239, 38261, 38273, 38281,
  409.     38287, 38299, 38303, 38317, 38321, 38327, 38329, 38333, 38351, 38371,
  410.     38377, 38393, 38431, 38447, 38449, 38453, 38459, 38461, 38501, 38543,
  411.     38557, 38561, 38567, 38569, 38593, 38603, 38609, 38611, 38629, 38639,
  412.     38651, 38653, 38669, 38671, 38677, 38693, 38699, 38707, 38711, 38713,
  413.     38723, 38729, 38737, 38747, 38749, 38767, 38783, 38791, 38803, 38821,
  414.     38833, 38839, 38851, 38861, 38867, 38873, 38891, 38903, 38917, 38921,
  415.     38923, 38933, 38953, 38959, 38971, 38977, 38993, 39019, 39023, 39041,
  416.     39043, 39047, 39079, 39089, 39097, 39103, 39107, 39113, 39119, 39133,
  417.     39139, 39157, 39161, 39163, 39181, 39191, 39199, 39209, 39217, 39227,
  418.     39229, 39233, 39239, 39241, 39251, 39293, 39301, 39313, 39317, 39323,
  419.     39341, 39343, 39359, 39367, 39371, 39373, 39383, 39397, 39409, 39419,
  420.     39439, 39443, 39451, 39461, 39499, 39503, 39509, 39511, 39521, 39541,
  421.     39551, 39563, 39569, 39581, 39607, 39619, 39623, 39631, 39659, 39667,
  422.     39671, 39679, 39703, 39709, 39719, 39727, 39733, 39749, 39761, 39769,
  423.     39779, 39791, 39799, 39821, 39827, 39829, 39839, 39841, 39847, 39857,
  424.     39863, 39869, 39877, 39883, 39887, 39901, 39929, 39937, 39953, 39971,
  425.     39979, 39983, 39989, 40009, 40013, 40031, 40037, 40039, 40063, 40087,
  426.     40093, 40099, 40111, 40123, 40127, 40129, 40151, 40153, 40163, 40169,
  427.     40177, 40189, 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283,
  428.     40289, 40343, 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433,
  429.     40459, 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529, 40531,
  430.     40543, 40559, 40577, 40583, 40591, 40597, 40609, 40627, 40637, 40639,
  431.     40693, 40697, 40699, 40709, 40739, 40751, 40759, 40763, 40771, 40787,
  432.     40801, 40813, 40819, 40823, 40829, 40841, 40847, 40849, 40853, 40867,
  433.     40879, 40883, 40897, 40903, 40927, 40933, 40939, 40949, 40961, 40973,
  434.     40993, 41011, 41017, 41023, 41039, 41047, 41051, 41057, 41077, 41081,
  435.     41113, 41117, 41131, 41141, 41143, 41149, 41161, 41177, 41179, 41183,
  436.     41189, 41201, 41203, 41213, 41221, 41227, 41231, 41233, 41243, 41257,
  437.     41263, 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381, 41387,
  438.     41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479, 41491, 41507,
  439.     41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593, 41597, 41603,
  440.     41609, 41611, 41617, 41621, 41627, 41641, 41647, 41651, 41659, 41669,
  441.     41681, 41687, 41719, 41729, 41737, 41759, 41761, 41771, 41777, 41801,
  442.     41809, 41813, 41843, 41849, 41851, 41863, 41879, 41887, 41893, 41897,
  443.     41903, 41911, 41927, 41941, 41947, 41953, 41957, 41959, 41969, 41981,
  444.     41983, 41999, 42013, 42017, 42019, 42023, 42043, 42061, 42071, 42073,
  445.     42083, 42089, 42101, 42131, 42139, 42157, 42169, 42179, 42181, 42187,
  446.     42193, 42197, 42209, 42221, 42223, 42227, 42239, 42257, 42281, 42283,
  447.     42293, 42299, 42307, 42323, 42331, 42337, 42349, 42359, 42373, 42379,
  448.     42391, 42397, 42403, 42407, 42409, 42433, 42437, 42443, 42451, 42457,
  449.     42461, 42463, 42467, 42473, 42487, 42491, 42499, 42509, 42533, 42557,
  450.     42569, 42571, 42577, 42589, 42611, 42641, 42643, 42649, 42667, 42677,
  451.     42683, 42689, 42697, 42701, 42703, 42709, 42719, 42727, 42737, 42743,
  452.     42751, 42767, 42773, 42787, 42793, 42797, 42821, 42829, 42839, 42841,
  453.     42853, 42859, 42863, 42899, 42901, 42923, 42929, 42937, 42943, 42953,
  454.     42961, 42967, 42979, 42989, 43003, 43013, 43019, 43037, 43049, 43051,
  455.     43063, 43067, 43093, 43103, 43117, 43133, 43151, 43159, 43177, 43189,
  456.     43201, 43207, 43223, 43237, 43261, 43271, 43283, 43291, 43313, 43319,
  457.     43321, 43331, 43391, 43397, 43399, 43403, 43411, 43427, 43441, 43451,
  458.     43457, 43481, 43487, 43499, 43517, 43541, 43543, 43573, 43577, 43579,
  459.     43591, 43597, 43607, 43609, 43613, 43627, 43633, 43649, 43651, 43661,
  460.     43669, 43691, 43711, 43717, 43721, 43753, 43759, 43777, 43781, 43783,
  461.     43787, 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913, 43933,
  462.     43943, 43951, 43961, 43963, 43969, 43973, 43987, 43991, 43997, 44017,
  463.     44021, 44027, 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101,
  464.     44111, 44119, 44123, 44129, 44131, 44159, 44171, 44179, 44189, 44201,
  465.     44203, 44207, 44221, 44249, 44257, 44263, 44267, 44269, 44273, 44279,
  466.     44281, 44293, 44351, 44357, 44371, 44381, 44383, 44389, 44417, 44449,
  467.     44453, 44483, 44491, 44497, 44501, 44507, 44519, 44531, 44533, 44537,
  468.     44543, 44549, 44563, 44579, 44587, 44617, 44621, 44623, 44633, 44641,
  469.     44647, 44651, 44657, 44683, 44687, 44699, 44701, 44711, 44729, 44741,
  470.     44753, 44771, 44773, 44777, 44789, 44797, 44809, 44819, 44839, 44843,
  471.     44851, 44867, 44879, 44887, 44893, 44909, 44917, 44927, 44939, 44953,
  472.     44959, 44963, 44971, 44983, 44987, 45007, 45013, 45053, 45061, 45077,
  473.     45083, 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179, 45181,
  474.     45191, 45197, 45233, 45247, 45259, 45263, 45281, 45289, 45293, 45307,
  475.     45317, 45319, 45329, 45337, 45341, 45343, 45361, 45377, 45389, 45403,
  476.     45413, 45427, 45433, 45439, 45481, 45491, 45497, 45503, 45523, 45533,
  477.     45541, 45553, 45557, 45569, 45587, 45589, 45599, 45613, 45631, 45641,
  478.     45659, 45667, 45673, 45677, 45691, 45697, 45707, 45737, 45751, 45757,
  479.     45763, 45767, 45779, 45817, 45821, 45823, 45827, 45833, 45841, 45853,
  480.     45863, 45869, 45887, 45893, 45943, 45949, 45953, 45959, 45971, 45979,
  481.     45989, 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093, 46099,
  482.     46103, 46133, 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199,
  483.     46219, 46229, 46237, 46261, 46271, 46273, 46279, 46301, 46307, 46309,
  484.     46327, 46337, 46349, 46351, 46381, 46399, 46411, 46439, 46441, 46447,
  485.     46451, 46457, 46471, 46477, 46489, 46499, 46507, 46511, 46523, 46549,
  486.     46559, 46567, 46573, 46589, 46591, 46601, 46619, 46633, 46639, 46643,
  487.     46649, 46663, 46679, 46681, 46687, 46691, 46703, 46723, 46727, 46747,
  488.     46751, 46757, 46769, 46771, 46807, 46811, 46817, 46819, 46829, 46831,
  489.     46853, 46861, 46867, 46877, 46889, 46901, 46919, 46933, 46957, 46993,
  490.     46997, 47017, 47041, 47051, 47057, 47059, 47087, 47093, 47111, 47119,
  491.     47123, 47129, 47137, 47143, 47147, 47149, 47161, 47189, 47207, 47221,
  492.     47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303, 47309, 47317,
  493.     47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417, 47419,
  494.     47431, 47441, 47459, 47491, 47497, 47501, 47507, 47513, 47521, 47527,
  495.     47533, 47543, 47563, 47569, 47581, 47591, 47599, 47609, 47623, 47629,
  496.     47639, 47653, 47657, 47659, 47681, 47699, 47701, 47711, 47713, 47717,
  497.     47737, 47741, 47743, 47777, 47779, 47791, 47797, 47807, 47809, 47819,
  498.     47837, 47843, 47857, 47869, 47881, 47903, 47911, 47917, 47933, 47939,
  499.     47947, 47951, 47963, 47969, 47977, 47981, 48017, 48023, 48029, 48049,
  500.     48073, 48079, 48091, 48109, 48119, 48121, 48131, 48157, 48163, 48179,
  501.     48187, 48193, 48197, 48221, 48239, 48247, 48259, 48271, 48281, 48299,
  502.     48311, 48313, 48337, 48341, 48353, 48371, 48383, 48397, 48407, 48409,
  503.     48413, 48437, 48449, 48463, 48473, 48479, 48481, 48487, 48491, 48497,
  504.     48523, 48527, 48533, 48539, 48541, 48563, 48571, 48589, 48593, 48611,
  505.     48619, 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731, 48733,
  506.     48751, 48757, 48761, 48767, 48779, 48781, 48787, 48799, 48809, 48817,
  507.     48821, 48823, 48847, 48857, 48859, 48869, 48871, 48883, 48889, 48907,
  508.     48947, 48953, 48973, 48989, 48991, 49003, 49009, 49019, 49031, 49033,
  509.     49037, 49043, 49057, 49069, 49081, 49103, 49109, 49117, 49121, 49123,
  510.     49139, 49157, 49169, 49171, 49177, 49193, 49199, 49201, 49207, 49211,
  511.     49223, 49253, 49261, 49277, 49279, 49297, 49307, 49331, 49333, 49339,
  512.     49363, 49367, 49369, 49391, 49393, 49409, 49411, 49417, 49429, 49433,
  513.     49451, 49459, 49463, 49477, 49481, 49499, 49523, 49529, 49531, 49537,
  514.     49547, 49549, 49559, 49597, 49603, 49613, 49627, 49633, 49639, 49663,
  515.     49667, 49669, 49681, 49697, 49711, 49727, 49739, 49741, 49747, 49757,
  516.     49783, 49787, 49789, 49801, 49807, 49811, 49823, 49831, 49843, 49853,
  517.     49871, 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957,
  518.     49991, 49993, 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069,
  519.     50077, 50087, 50093, 50101, 50111, 50119, 50123, 50129, 50131, 50147,
  520.     50153, 50159, 50177, 50207, 50221, 50227, 50231, 50261, 50263, 50273,
  521.     50287, 50291, 50311, 50321, 50329, 50333, 50341, 50359, 50363, 50377,
  522.     50383, 50387, 50411, 50417, 50423, 50441, 50459, 50461, 50497, 50503,
  523.     50513, 50527, 50539, 50543, 50549, 50551, 50581, 50587, 50591, 50593,
  524.     50599, 50627, 50647, 50651, 50671, 50683, 50707, 50723, 50741, 50753,
  525.     50767, 50773, 50777, 50789, 50821, 50833, 50839, 50849, 50857, 50867,
  526.     50873, 50891, 50893, 50909, 50923, 50929, 50951, 50957, 50969, 50971,
  527.     50989, 50993, 51001, 51031, 51043, 51047, 51059, 51061, 51071, 51109,
  528.     51131, 51133, 51137, 51151, 51157, 51169, 51193, 51197, 51199, 51203,
  529.     51217, 51229, 51239, 51241, 51257, 51263, 51283, 51287, 51307, 51329,
  530.     51341, 51343, 51347, 51349, 51361, 51383, 51407, 51413, 51419, 51421,
  531.     51427, 51431, 51437, 51439, 51449, 51461, 51473, 51479, 51481, 51487,
  532.     51503, 51511, 51517, 51521, 51539, 51551, 51563, 51577, 51581, 51593,
  533.     51599, 51607, 51613, 51631, 51637, 51647, 51659, 51673, 51679, 51683,
  534.     51691, 51713, 51719, 51721, 51749, 51767, 51769, 51787, 51797, 51803,
  535.     51817, 51827, 51829, 51839, 51853, 51859, 51869, 51871, 51893, 51899,
  536.     51907, 51913, 51929, 51941, 51949, 51971, 51973, 51977, 51991, 52009,
  537.     52021, 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121, 52127,
  538.     52147, 52153, 52163, 52177, 52181, 52183, 52189, 52201, 52223, 52237,
  539.     52249, 52253, 52259, 52267, 52289, 52291, 52301, 52313, 52321, 52361,
  540.     52363, 52369, 52379, 52387, 52391, 52433, 52453, 52457, 52489, 52501,
  541.     52511, 52517, 52529, 52541, 52543, 52553, 52561, 52567, 52571, 52579,
  542.     52583, 52609, 52627, 52631, 52639, 52667, 52673, 52691, 52697, 52709,
  543.     52711, 52721, 52727, 52733, 52747, 52757, 52769, 52783, 52807, 52813,
  544.     52817, 52837, 52859, 52861, 52879, 52883, 52889, 52901, 52903, 52919,
  545.     52937, 52951, 52957, 52963, 52967, 52973, 52981, 52999, 53003, 53017,
  546.     53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101, 53113, 53117,
  547.     53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197, 53201, 53231,
  548.     53233, 53239, 53267, 53269, 53279, 53281, 53299, 53309, 53323, 53327,
  549.     53353, 53359, 53377, 53381, 53401, 53407, 53411, 53419, 53437, 53441,
  550.     53453, 53479, 53503, 53507, 53527, 53549, 53551, 53569, 53591, 53593,
  551.     53597, 53609, 53611, 53617, 53623, 53629, 53633, 53639, 53653, 53657,
  552.     53681, 53693, 53699, 53717, 53719, 53731, 53759, 53773, 53777, 53783,
  553.     53791, 53813, 53819, 53831, 53849, 53857, 53861, 53881, 53887, 53891,
  554.     53897, 53899, 53917, 53923, 53927, 53939, 53951, 53959, 53987, 53993,
  555.     54001, 54011, 54013, 54037, 54049, 54059, 54083, 54091, 54101, 54121,
  556.     54133, 54139, 54151, 54163, 54167, 54181, 54193, 54217, 54251, 54269,
  557.     54277, 54287, 54293, 54311, 54319, 54323, 54331, 54347, 54361, 54367,
  558.     54371, 54377, 54401, 54403, 54409, 54413, 54419, 54421, 54437, 54443,
  559.     54449, 54469, 54493, 54497, 54499, 54503, 54517, 54521, 54539, 54541,
  560.     54547, 54559, 54563, 54577, 54581, 54583, 54601, 54617, 54623, 54629,
  561.     54631, 54647, 54667, 54673, 54679, 54709, 54713, 54721, 54727, 54751,
  562.     54767, 54773, 54779, 54787, 54799, 54829, 54833, 54851, 54869, 54877,
  563.     54881, 54907, 54917, 54919, 54941, 54949, 54959, 54973, 54979, 54983,
  564.     55001, 55009, 55021, 55049, 55051, 55057, 55061, 55073, 55079, 55103,
  565.     55109, 55117, 55127, 55147, 55163, 55171, 55201, 55207, 55213, 55217,
  566.     55219, 55229, 55243, 55249, 55259, 55291, 55313, 55331, 55333, 55337,
  567.     55339, 55343, 55351, 55373, 55381, 55399, 55411, 55439, 55441, 55457,
  568.     55469, 55487, 55501, 55511, 55529, 55541, 55547, 55579, 55589, 55603,
  569.     55609, 55619, 55621, 55631, 55633, 55639, 55661, 55663, 55667, 55673,
  570.     55681, 55691, 55697, 55711, 55717, 55721, 55733, 55763, 55787, 55793,
  571.     55799, 55807, 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849,
  572.     55871, 55889, 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949,
  573.     55967, 55987, 55997, 56003, 56009, 56039, 56041, 56053, 56081, 56087,
  574.     56093, 56099, 56101, 56113, 56123, 56131, 56149, 56167, 56171, 56179,
  575.     56197, 56207, 56209, 56237, 56239, 56249, 56263, 56267, 56269, 56299,
  576.     56311, 56333, 56359, 56369, 56377, 56383, 56393, 56401, 56417, 56431,
  577.     56437, 56443, 56453, 56467, 56473, 56477, 56479, 56489, 56501, 56503,
  578.     56509, 56519, 56527, 56531, 56533, 56543, 56569, 56591, 56597, 56599,
  579.     56611, 56629, 56633, 56659, 56663, 56671, 56681, 56687, 56701, 56711,
  580.     56713, 56731, 56737, 56747, 56767, 56773, 56779, 56783, 56807, 56809,
  581.     56813, 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897, 56909,
  582.     56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963, 56983, 56989,
  583.     56993, 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097,
  584.     57107, 57119, 57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191,
  585.     57193, 57203, 57221, 57223, 57241, 57251, 57259, 57269, 57271, 57283,
  586.     57287, 57301, 57329, 57331, 57347, 57349, 57367, 57373, 57383, 57389,
  587.     57397, 57413, 57427, 57457, 57467, 57487, 57493, 57503, 57527, 57529,
  588.     57557, 57559, 57571, 57587, 57593, 57601, 57637, 57641, 57649, 57653,
  589.     57667, 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731, 57737,
  590.     57751, 57773, 57781, 57787, 57791, 57793, 57803, 57809, 57829, 57839,
  591.     57847, 57853, 57859, 57881, 57899, 57901, 57917, 57923, 57943, 57947,
  592.     57973, 57977, 57991, 58013, 58027, 58031, 58043, 58049, 58057, 58061,
  593.     58067, 58073, 58099, 58109, 58111, 58129, 58147, 58151, 58153, 58169,
  594.     58171, 58189, 58193, 58199, 58207, 58211, 58217, 58229, 58231, 58237,
  595.     58243, 58271, 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379,
  596.     58391, 58393, 58403, 58411, 58417, 58427, 58439, 58441, 58451, 58453,
  597.     58477, 58481, 58511, 58537, 58543, 58549, 58567, 58573, 58579, 58601,
  598.     58603, 58613, 58631, 58657, 58661, 58679, 58687, 58693, 58699, 58711,
  599.     58727, 58733, 58741, 58757, 58763, 58771, 58787, 58789, 58831, 58889,
  600.     58897, 58901, 58907, 58909, 58913, 58921, 58937, 58943, 58963, 58967,
  601.     58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051, 59053,
  602.     59063, 59069, 59077, 59083, 59093, 59107, 59113, 59119, 59123, 59141,
  603.     59149, 59159, 59167, 59183, 59197, 59207, 59209, 59219, 59221, 59233,
  604.     59239, 59243, 59263, 59273, 59281, 59333, 59341, 59351, 59357, 59359,
  605.     59369, 59377, 59387, 59393, 59399, 59407, 59417, 59419, 59441, 59443,
  606.     59447, 59453, 59467, 59471, 59473, 59497, 59509, 59513, 59539, 59557,
  607.     59561, 59567, 59581, 59611, 59617, 59621, 59627, 59629, 59651, 59659,
  608.     59663, 59669, 59671, 59693, 59699, 59707, 59723, 59729, 59743, 59747,
  609.     59753, 59771, 59779, 59791, 59797, 59809, 59833, 59863, 59879, 59887,
  610.     59921, 59929, 59951, 59957, 59971, 59981, 59999, 60013, 60017, 60029,
  611.     60037, 60041, 60077, 60083, 60089, 60091, 60101, 60103, 60107, 60127,
  612.     60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217, 60223, 60251,
  613.     60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343, 60353,
  614.     60373, 60383, 60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497,
  615.     60509, 60521, 60527, 60539, 60589, 60601, 60607, 60611, 60617, 60623,
  616.     60631, 60637, 60647, 60649, 60659, 60661, 60679, 60689, 60703, 60719,
  617.     60727, 60733, 60737, 60757, 60761, 60763, 60773, 60779, 60793, 60811,
  618.     60821, 60859, 60869, 60887, 60889, 60899, 60901, 60913, 60917, 60919,
  619.     60923, 60937, 60943, 60953, 60961, 61001, 61007, 61027, 61031, 61043,
  620.     61051, 61057, 61091, 61099, 61121, 61129, 61141, 61151, 61153, 61169,
  621.     61211, 61223, 61231, 61253, 61261, 61283, 61291, 61297, 61331, 61333,
  622.     61339, 61343, 61357, 61363, 61379, 61381, 61403, 61409, 61417, 61441,
  623.     61463, 61469, 61471, 61483, 61487, 61493, 61507, 61511, 61519, 61543,
  624.     61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613, 61627, 61631,
  625.     61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717,
  626.     61723, 61729, 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861,
  627.     61871, 61879, 61909, 61927, 61933, 61949, 61961, 61967, 61979, 61981,
  628.     61987, 61991, 62003, 62011, 62017, 62039, 62047, 62053, 62057, 62071,
  629.     62081, 62099, 62119, 62129, 62131, 62137, 62141, 62143, 62171, 62189,
  630.     62191, 62201, 62207, 62213, 62219, 62233, 62273, 62297, 62299, 62303,
  631.     62311, 62323, 62327, 62347, 62351, 62383, 62401, 62417, 62423, 62459,
  632.     62467, 62473, 62477, 62483, 62497, 62501, 62507, 62533, 62539, 62549,
  633.     62563, 62581, 62591, 62597, 62603, 62617, 62627, 62633, 62639, 62653,
  634.     62659, 62683, 62687, 62701, 62723, 62731, 62743, 62753, 62761, 62773,
  635.     62791, 62801, 62819, 62827, 62851, 62861, 62869, 62873, 62897, 62903,
  636.     62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983, 62987, 62989,
  637.     63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127,
  638.     63131, 63149, 63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281,
  639.     63299, 63311, 63313, 63317, 63331, 63337, 63347, 63353, 63361, 63367,
  640.     63377, 63389, 63391, 63397, 63409, 63419, 63421, 63439, 63443, 63463,
  641.     63467, 63473, 63487, 63493, 63499, 63521, 63527, 63533, 63541, 63559,
  642.     63577, 63587, 63589, 63599, 63601, 63607, 63611, 63617, 63629, 63647,
  643.     63649, 63659, 63667, 63671, 63689, 63691, 63697, 63703, 63709, 63719,
  644.     63727, 63737, 63743, 63761, 63773, 63781, 63793, 63799, 63803, 63809,
  645.     63823, 63839, 63841, 63853, 63857, 63863, 63901, 63907, 63913, 63929,
  646.     63949, 63977, 63997, 64007, 64013, 64019, 64033, 64037, 64063, 64067,
  647.     64081, 64091, 64109, 64123, 64151, 64153, 64157, 64171, 64187, 64189,
  648.     64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301, 64303, 64319,
  649.     64327, 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453,
  650.     64483, 64489, 64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601,
  651.     64609, 64613, 64621, 64627, 64633, 64661, 64663, 64667, 64679, 64693,
  652.     64709, 64717, 64747, 64763, 64781, 64783, 64793, 64811, 64817, 64849,
  653.     64853, 64871, 64877, 64879, 64891, 64901, 64919, 64921, 64927, 64937,
  654.     64951, 64969, 64997, 65003, 65011, 65027, 65029, 65033, 65053, 65063,
  655.     65071, 65089, 65099, 65101, 65111, 65119, 65123, 65129, 65141, 65147,
  656.     65167, 65171, 65173, 65179, 65183, 65203, 65213, 65239, 65257, 65267,
  657.     65269, 65287, 65293, 65309, 65323, 65327, 65353, 65357, 65371, 65381,
  658.     65393, 65407, 65413, 65419, 65423, 65437, 65447, 65449, 65479, 65497,
  659.     65519, 65521
  660. };
  661.  
  662. const unsigned int kTotNPrimiInTab = sizeof(kTabNp)/sizeof(*kTabNp);
  663.  
  664. #endif // TABELLA_NUMERI_PRIMI_65535_H_INCLUDED


E' stato anche necessario "esporre" nel file interfaccia.h il prototipo della funzione
void mostra_errore_in_console(), rimuovendolo dal file interfaccia.c.

Ultima modifica effettuata da AldoBaldo il 08/01/2017 alle 11:30

ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 700
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 10:30
Venerdì, 06/01/2017
Ho voluto provare a prendere in considerazione un altro dei suggerimenti di TheDarkJuster, eliminando gran parte dell'interfaccia, ricavando il dato da scomporre da argc e argv, e fornendo il risultato solo nella versione "in riga" (cassando quindi il calcolo in colonna).

Lanciando il programma con "esegui..." su windows il programma funziona, ma la console si chiude non appena il printf() ritorna. Per evitare questo comportamento avrei dovuto aggiungere un bel system("pause"), ma mi han detto che è brutto, cattivo, cacca, diavolo, quindi ho lasciato perdere. Persone informate sostengono che, se non ho capito male, in linux non esiste il problema della chiusura della console, per cui in quell'ambiente dovrebbe funzionare. Purtroppo non ho modo di testare... qualcuno lo fa al posto mio e poi mi dice com'è andata?

In questa versione del programma occorre conservere il file tabella_numeri_primi_65535.h, eliminare i file interfaccia.h e interfaccia.c, e impiegare questo nuovo main.c:

File main.c

Codice sorgente - presumibilmente C++
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "tabella_numeri_primi_65535.h"
  5.  
  6. // ===> MACRO/COSTANTI/STRINGHE <===============================================
  7.  
  8. #define MAX_FATTORI 36 // in effetti, unsigned long puo' contenere un valore
  9.                        // massimo di 2^32-1, per cui nella scomposizione non
  10.                        // ci possono essere piu' di 32 fattori primi
  11.  
  12. // ===> PROTOTIPI DI FUNZIONI <=================================================
  13.  
  14. int scomponi( unsigned long n, unsigned long *fattori );
  15. int chiedi_numero_da_scomporre( int argc, char *argv[], unsigned long *n );
  16. int stringa_in_numero_intero( const char *s, unsigned long *n );
  17. void scrivi_scomposizione_in_linea( unsigned long n, unsigned long *fattori );
  18. void mostra_errore( const char *msg );
  19.  
  20. // ===> FUNZIONE D'ACCESSO AL PROGRAMMA <=======================================
  21.  
  22. int main( int argc, char *argv[] ) {
  23.     unsigned long n, fattori[MAX_FATTORI];
  24.  
  25.     memset( fattori, 0, sizeof(*fattori)*MAX_FATTORI );
  26.  
  27.     if( chiedi_numero_da_scomporre(argc,argv,&n) == 0 ) {
  28.         if( scomponi(n,fattori) == 0 )
  29.             scrivi_scomposizione_in_linea( n, fattori );
  30.     } else mostra_errore( "input non valido" );
  31.  
  32.     return 0;
  33. }
  34.  
  35. // ===> FUNZIONE DI SCOMPOSIZIONE IN FATTORI PRIMI <============================
  36.  
  37. int scomponi( unsigned long n, unsigned long *fattori ) {
  38.     if( n > 1 ) {
  39.         int i_np = 0; // i_np = indice del numero primo
  40.         int i_ft = 0; // i_ft = indice del fattore
  41.         unsigned long dc = kTabNp[i_np]; // dc = divisore corrente
  42.  
  43.         while( n!=1 ) {
  44.             if( n%dc ) {
  45.                 dc = kTabNp[++i_np];
  46.             }
  47.             else {
  48.                 fattori[i_ft++] = dc;
  49.                 n /= dc;
  50.             }
  51.         }
  52.  
  53.         return 0;
  54.     }
  55.     else {
  56.         if( n == 0 )
  57.             mostra_errore( "lo zero non e' scomponibile" );
  58.         else mostra_errore( "l'unita' non e' scomponibile" );
  59.  
  60.         return 1;
  61.     }
  62. }
  63.  
  64. // ===> FUNZIONI DI INTERFACCIA <==============================================
  65.  
  66. /*==============================================================================
  67. Verifica che la linea di comando contenga parametri validi, ovvero due parametri
  68. dei quali il secondo sia un numero intero. La verifica del secondo parametro
  69. avviene tramite la funzione standard strtoul().
  70. ==============================================================================*/
  71.  
  72. int chiedi_numero_da_scomporre( int argc, char *argv[], unsigned long *n ) {
  73.     if( argc == 2 )
  74.         return stringa_in_numero_intero(argv[1],n) != 0;
  75.     else return 1;
  76. }
  77.  
  78. /*==============================================================================
  79. Tramile la funzione standard strtoul() tenta di verificare la validita' della
  80. stringa immessa dall'utente. Restituisce in *n il numero intero senza segno
  81. rappresentato dalla stringa s. Se tutto va bene, il valore di ritorno e' 0; in
  82. caso contrario e' diverso da 0.
  83. ==============================================================================*/
  84.  
  85. int stringa_in_numero_intero( const char *s, unsigned long *n ) {
  86.     char *fine = NULL;
  87.     *n = strtoul( s, &fine, 10 );
  88.     return s == fine;
  89. }
  90.  
  91. /*==============================================================================
  92. Scrive nella console una formula che descrive la scomposizione in fattori del
  93. numero n, secondo i dati immagazzinati nell'array fattori.
  94. ==============================================================================*/
  95.  
  96. void scrivi_scomposizione_in_linea( unsigned long n, unsigned long *fattori ) {
  97.     unsigned long fc = 0; // fc = fattore corrente
  98.     int ec = 0;           // ec = esponente corrente
  99.     int tf;               // tf = totale fattori
  100.     int i;                // un contatore
  101.  
  102.     for( tf=0; fattori[tf]!=0; ++tf );
  103.     if( tf == 0 ) return;
  104.  
  105.     printf( "%lu = ", n );
  106.  
  107.     for( i=tf-1, fc=fattori[i], ec=0; i>=0; --i ) {
  108.         if( fc != fattori[i] ) {
  109.             printf( "%lu", fc );
  110.             if( ec != 1 ) printf( "^%d", ec );
  111.             printf( " * " );
  112.  
  113.             fc = fattori[i];
  114.             ec = 1;
  115.         }
  116.         else {
  117.             ++ec;
  118.         }
  119.     }
  120.  
  121.     printf( "%lu", fc );
  122.     if( ec != 1 ) printf( "^%d", ec );
  123.     printf( "\n" );
  124. }
  125.  
  126. /*==============================================================================
  127. Scrive nella console la stringa msg, preceduta da una breve intestazione
  128. d'errore. Emette un "bip" sonoro d'avviso.
  129. ==============================================================================*/
  130.  
  131. void mostra_errore( const char *msg ) {
  132.     if( msg ) printf( "\a\nERRORE: %s\n\n", msg );
  133. }

ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 12:43
Venerdì, 06/01/2017
Su windows fai esegui.... scrivi cmd.exe e si apre la console. In quella digiti il percorso del file eseguibile e non hai problemi di chiusura della console. Proprio come in ambienti unix.......

PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 700
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 14:06
Venerdì, 06/01/2017
Ma dai, hai ragione! Ci ho provato e funziona proprio come i comandi del DOS. Non ne avevo idea.

P.S. ...e funziona anche omettendo il ".exe" alla fine del nome del programma.

ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 700
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 14:56
Venerdì, 06/01/2017
A questo punto, però, ho cambiato di nuovo il file main.c in modo che chi richiede la scomposizione possa ottenerela con o senza la versione "in colonna". Con una linea di comando tipo "scomponi 132" viene fornita in output la sola versione "in linea" della scomposizione; con una linea di comando tipo "scomponi 132 c" viene fornita in output anche la versione "in colonna" della scomposizione. "C" (maiuscolo o minuscolo è lo stesso) sta ovviamente per "colonna". Quale che sia la stringa usata come terzo parametro, se c'è, ne viene valutato sempre e soltanto il primo carattere, per cui scrivere "c", "colonna", "cane", "Calogero"... è del tutto equivalente. Ovviamente scrivere "pippo" significa scrivere non c, quindi si ottiene solo la versione "in linea" della scomposizione. Eventuali parametri oltre il terzo vengono ignorati.

TheDarkJuster, mi hai fatto scoprire una cosa molto interessante.

File main.c

Codice sorgente - presumibilmente C++
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5. #include "tabella_numeri_primi_65535.h"
  6.  
  7. // ===> MACRO/COSTANTI/STRINGHE <===============================================
  8.  
  9. #define MAX_FATTORI 36 // in effetti, unsigned long puo' contenere un valore
  10.                        // massimo di 2^32-1, per cui nella scomposizione non
  11.                        // ci possono essere piu' di 32 fattori primi
  12.  
  13. enum { // codici d'errore
  14.     kErrNoErr,
  15.     kErrParametriInsufficienti,
  16.     kErrParametroNonNumerico,
  17.     kErrZeroNonScomponibile,
  18.     kErrUnitaNonScomponibile
  19. };
  20.  
  21. const char *kStrErr[] = {
  22.     "",
  23.     "e' richiesto almeno un parametro",
  24.     "il primo parametro dev'essere un valore numerico",
  25.     "lo zero non e' scomponibile",
  26.     "l'unita' non e' scomponibile"
  27. };
  28.  
  29. const int kMaxErr = sizeof(kStrErr) / sizeof(*kStrErr);
  30.  
  31. // ===> PROTOTIPI DI FUNZIONI <=================================================
  32.  
  33. int scomponi( unsigned long n, unsigned long *fattori );
  34. int chiedi_parametri( int argc, char *argv[], unsigned long *n, int *tOut );
  35. int stringa_in_numero_intero( const char *s, unsigned long *n );
  36. void output_in_colonna( unsigned long n, unsigned long *fattori );
  37. void output_in_linea( unsigned long n, unsigned long *fattori );
  38. void mostra_errore( int codice );
  39.  
  40. // ===> FUNZIONE D'ACCESSO AL PROGRAMMA <=======================================
  41.  
  42. int main( int argc, char *argv[] ) {
  43.     unsigned long n, fattori[MAX_FATTORI];
  44.     int tOut; // tOut == 0: output solo in linea
  45.               // tOut != 0: output anche in colonna
  46.     int errore;
  47.  
  48.     memset( fattori, 0, sizeof(*fattori)*MAX_FATTORI );
  49.  
  50.     if( (errore=chiedi_parametri(argc,argv,&n,&tOut)) == kErrNoErr ) {
  51.         if( (errore=scomponi(n,fattori)) == kErrNoErr ) {
  52.             if( tOut != 0 )
  53.                 output_in_colonna( n, fattori );
  54.             output_in_linea( n, fattori );
  55.         }
  56.     }
  57.  
  58.     mostra_errore( errore );
  59.  
  60.     return 0;
  61. }
  62.  
  63. // ===> FUNZIONE DI SCOMPOSIZIONE IN FATTORI PRIMI <============================
  64.  
  65. int scomponi( unsigned long n, unsigned long *fattori ) {
  66.     if( n > 1 ) {
  67.         int i_np = 0; // i_np = indice del numero primo
  68.         int i_ft = 0; // i_ft = indice del fattore
  69.         unsigned long dc = kTabNp[i_np]; // dc = divisore corrente
  70.         unsigned long ld = sqrt(n);      // ld = limite divisore
  71.  
  72.         while( n!=1 ) {
  73.             if( n%dc )
  74.                 dc = dc<ld ? kTabNp[++i_np] : n;
  75.             else n /= (fattori[i_ft++]=dc);
  76.         }
  77.  
  78.         return kErrNoErr;
  79.     } else return n==0 ? kErrZeroNonScomponibile : kErrUnitaNonScomponibile;
  80. }
  81.  
  82. // ===> FUNZIONI DI INTERFACCIA <===============================================
  83.  
  84. /*==============================================================================
  85. Verifica che la linea di comando contenga parametri validi, ovvero due o tre
  86. parametri dei quali il secondo sia sempre un numero intero (la verifica del
  87. secondo parametro avviene tramite la funzione standard strtoul()) e il terzo,
  88. se presente, una stringa che identifichi il tipo di output richiesto.
  89. Se il terzo parametro e' una stringa che contiene come primo carattere una 'c'
  90. o una 'C', *tOut sara' impostato su 1 (il che indica una richiesta di fornire
  91. l'output anche nella forma in colonna); se il terzo parametro e' assente o NON
  92. inizia con una 'c' o con una 'C', *tOut sara' impostato su 0 (il che indica una
  93. richiesta di fornire l'output esclusivamente nella forma in linea).
  94. ==============================================================================*/
  95.  
  96. int chiedi_parametri( int argc, char *argv[], unsigned long *n, int *tOut ) {
  97.     if( argc > 1 ) {
  98.         if( stringa_in_numero_intero(argv[1],n) == 0 ) {
  99.             if( argc < 3 )
  100.                 *tOut = 0; // il tipo di output di default: solo in linea
  101.             else *tOut = ((*argv[2]=='c') || (*argv[2]=='C'));
  102.  
  103.             return kErrNoErr;
  104.         } else return kErrParametroNonNumerico;
  105.     } else return kErrParametriInsufficienti;
  106. }
  107.  
  108. /*==============================================================================
  109. Tramite la funzione standard strtoul() tenta di verificare la validita' della
  110. stringa immessa dall'utente. Restituisce in *n il numero intero senza segno
  111. rappresentato dalla stringa s. Se tutto va bene, il valore di ritorno e' 0; in
  112. caso contrario e' diverso da 0.
  113. ==============================================================================*/
  114.  
  115. int stringa_in_numero_intero( const char *s, unsigned long *n ) {
  116.     char *fine = NULL;
  117.     *n = strtoul( s, &fine, 10 );
  118.     return s != fine ? kErrNoErr : kErrParametroNonNumerico;
  119. }
  120.  
  121. /*==============================================================================
  122. Scrive nella console una tabella che raffigura il procedimento di scomposizione
  123. in fattori primi del numero n, secondo i dati immagazzinati nell'array fattori.
  124. ==============================================================================*/
  125.  
  126. void output_in_colonna( unsigned long n, unsigned long *fattori ){
  127.     int i;
  128.  
  129.     for( i=0; n!=1; ++i ) {
  130.         printf( "\n%12lu | %lu", n, fattori[i] );
  131.         n /= fattori[i];
  132.     }
  133.  
  134.     printf( "\n%12lu | \n", n );
  135. }
  136.  
  137. /*==============================================================================
  138. Scrive nella console una formula che descrive la scomposizione in fattori del
  139. numero n, secondo i dati immagazzinati nell'array fattori.
  140. ==============================================================================*/
  141.  
  142. void output_in_linea( unsigned long n, unsigned long *fattori ) {
  143.     unsigned long fc = 0; // fc = fattore corrente
  144.     int ec = 0;           // ec = esponente corrente
  145.     int tf;               // tf = totale fattori
  146.     int i;                // un contatore
  147.  
  148.     for( tf=0; fattori[tf]!=0; ++tf );
  149.     if( tf == 0 ) return;
  150.  
  151.     printf( "\n%12lu = ", n );
  152.  
  153.     for( i=tf-1, fc=fattori[i], ec=0; i>=0; --i ) {
  154.         if( fc != fattori[i] ) {
  155.             printf( "%lu", fc );
  156.             if( ec != 1 ) printf( "^%d", ec );
  157.             printf( " * " );
  158.  
  159.             fc = fattori[i];
  160.             ec = 1;
  161.         }
  162.         else {
  163.             ++ec;
  164.         }
  165.     }
  166.  
  167.     printf( "%lu", fc );
  168.     if( ec != 1 ) printf( "^%d", ec );
  169.     printf( "\n" );
  170. }
  171.  
  172. /*==============================================================================
  173. Scrive nella console la stringa d'errore abbinata al valore del parametro codice
  174. nell'ambito dell'array di stringhe kStrErr, preceduta da una breve intestazione.
  175. Emette un "bip" sonoro d'avviso.
  176. ==============================================================================*/
  177.  
  178. void mostra_errore( int codice ) {
  179.     if( codice != kErrNoErr ) {
  180.         if( codice > kErrNoErr && codice < kMaxErr )
  181.             printf( "\a\nERRORE: %s\n", kStrErr[codice] );
  182.         else printf( "\a\nERRORE: codice d'errore imprevisto: %d\n", codice );
  183.     }
  184. }


Edit (06/01/2017) - M'è venuto in mente un modo per ridurre le dimensioni dell'eseguibile: generare la tabella dei numeri primi nel file tabella_numeri_primi_65535.h non come array di unsigned long, ma come array di unsigned short. Le dimensioni vengono dimezzate e un unsigned short "porta" comunque valori fino a 65535, quindi non si perde alcuna informazione. Col mio compilatore l'exe è sceso da 35Kb a 22Kb.
Inoltre, trovato e corretto un errore grave proprio nella funzione scomponi().

Edit2 (08/01/2017) - Ho cambiato il limite per la ricerca del divisore nella funzione scomponi(); ora il calcolo dovrebbe essere più rapido in alcuni casi. Ho anche modificato il sistema di segnalazione degli errori per renderlo un po' più esplicito.

Ultima modifica effettuata da AldoBaldo il 08/01/2017 alle 10:18

ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 23:24
Venerdì, 06/01/2017
Rimpicciolire il più possibile il tipo di intero è sempre buona norma. Tra l'altro usando unsigned si possono usare metà combinazioni per estendere il numero massimo!

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo