prime.c

Calc Software Package for Number Calc

      4,  3,  6, 32,137,  0,  5,  8, 34,  5,144,  0, 64,  0,130,  9,
     80,  0,  0,  0,160, 65,194, 32,  8,  0, 22,  8, 64, 38, 33,208,
    144,  8,129,144, 65,  0,  2, 68,  8, 16, 12, 10,134,  9,144,  4,
      0,200,160,  4,  8, 48, 32,137,132,  0, 17, 34, 44, 64,  0,  8,
      2,176,  1, 72,  2,  1,  9, 32,  4,  3,  4,  0,128,  2, 96, 66,
     48, 33, 74, 16, 68,  9,  2,  0,  1, 36,  0, 18,130, 33,128,164,
     32, 16,  2,  4,145,160, 64, 24,  4,  0,  2,  6,105,  9,  0,  5,
     88,  2,  1,  0,  0, 72,  0,  0,  0,  3,146, 32,  0, 52,  1,200,
     32, 72,  8, 48,  8, 66,128, 32,145,144,104,  1,  4, 64, 18,  2,
     97,  0, 18,  8,  1,160,  0, 17,  4, 33, 72,  4, 36,146,  0, 12,
      1,132,  4,  0,  0,  1, 18,150, 64,  1,160, 65,136, 34, 40,136,
      0, 68, 66,128, 36, 18, 20,  1, 66,144, 96, 26, 16,  4,129, 16,
     72,  8,  6, 41,131,  2, 64,  2, 36,100,128, 16,  5,128, 16, 64,
      2,  2,  8, 66,132,  1,  9, 32,  4, 80,  0, 96, 17, 48, 64, 19,
      2,  4,129,  0,  9,  8, 32, 69, 74, 16, 97,144, 38, 12,  8,  2,
     33,145,  0, 96,  2,  4,  0,  2,  0, 12,  8,  6,  8, 72,132,  8,
     17,  2,  0,128,164,  0, 90, 32,  0,136,  4,  4,  2,  0,  9,  0,
     20,  8, 73, 20, 32,200,  0,  4,145,160, 64, 89,128,  0, 18, 16,
      0,128,128,101,  0,  0,  4,  0,128, 64, 25,  0, 33,  3,132, 96,
    192,  4, 36, 26, 18, 97,128,128,  8,  2,  4,  9, 66, 18, 32,  8,
     52,  4,144, 32,  1,  1,160,  0, 11,  0,  8,145,146, 64,  2, 52,
     64,136, 16, 97, 25,  2,  0, 64,  4, 37,192,128,104,  8,  4, 33,
    128, 34,  4,  0,160, 12,  1,132, 32, 65,  0,  8,138,  0, 32,138,
      0, 72,136,  4,  4, 17,130,  8, 64,134,  9, 73,164, 64,  0, 16,
      1,  1,162,  4, 80,128, 12,128,  0, 72,130,160,  1, 24, 18, 65,
      1,  4, 72, 65,  0, 36,  1,  0,  0,136, 20,  0,  2,  0,104,  1,
     32,  8, 74, 34,  8,131,128,  0,137,  4,  1,194,  0,  0,  0, 52,
      4,  0,130, 40,  2,  2, 65, 74,144,  5,130,  2,  9,128, 36,  4,
     65,  0,  1,146,128, 40,  1, 20,  0, 80, 32, 76, 16,176,  4, 67,
    164, 33,144,  4,  1,  2,  0, 68, 72,  0,100,  8,  6,  0, 66, 32,
      8,  2,146,  1, 74,  0, 32, 80, 50, 37,144, 34,  4,  9,  0,  8,
     17,128, 33,  1, 16,  5,  0, 50,  8,136,148,  8,  8, 36, 13,193,
    128, 64, 11, 32, 64, 24, 18,  4,  0, 34, 64, 16, 38,  5,193,130,
      0,  1, 48, 36,  2, 34, 65,  8, 36, 72, 26,  0, 37,210, 18, 40,
     66,  0,  4, 64, 48, 65,  0,  2,  0, 19, 32, 36,209,132,  8,137,
    128,  4, 82,  0, 68, 24,164,  0,  0,  6, 32,145, 16,  9, 66, 32,
     36, 64, 48, 40,  0,132, 64, 64,128,  8, 16,  4,  9,  8,  4, 64,
      8, 34,  0, 25,  2,  0,  0,128, 44,  2,  2, 33,  1,144, 32, 64,
      0, 12,  0, 52, 72, 88, 32,  1, 67,  4, 32,128, 20,  0,144,  0,
    109, 17,  0,  0, 64, 32,  0,  3, 16, 64,136, 48,  5, 74,  0,101,
     16, 36,  8, 24,132, 40,  3,128, 32, 66,176, 64,  0, 16,105, 25,
      4,  0,  0,128,  4,194,  4,  0,  1,  0,  5,  0, 34, 37,  8,150,
      4,  2, 34,  0,208, 16, 41,  1,160, 96,  8, 16,  4,  1, 22, 68,
     16,  2, 40,  2,130, 72, 64,132, 32,144, 34, 40,128,  4,  0, 64,
      4, 36,  0,128, 41,  3, 16, 96, 72,  0,  0,129,160,  0, 81, 32,
     12,209,  0,  1, 65, 32,  4,146,  0,  0, 16,146,  0, 66,  4,  5,
      1,134, 64,128, 16, 32, 82, 32, 33,  0, 16, 72, 10,  2,  0,208,
     18, 65, 72,128,  4,  0,  0, 72,  9, 34,  4,  0, 36,  0, 67, 16,
     96, 10,  0, 68, 18, 32, 44,  8, 32, 68,  0,132,  9, 64,  6,  8,
    193,  0, 64,128, 32,  0,152, 18, 72, 16,162, 32,  0,132, 72,192,
     16, 32,144, 18,  8,152,130,  0, 10,160,  4,  3,  0, 40,195,  0,
     68, 66, 16,  4,  8,  4, 64,  0,  0,  5, 16,  0, 33,  3,128,  4,
    136, 18,105, 16,  0,  4,  8,  4,  4,  2,132, 72, 73,  4, 32, 24,
      2,100,128, 48,  8,  1,  2,  0, 82, 18, 73,  8, 32, 65,136, 16,
     72,  8, 52,  0,  1,134,  5,208,  0,  0,131,132, 33, 64,  2, 65,
     16,128, 72, 64,162, 32, 81,  0,  0, 73,  0,  1,144, 32, 64, 24,
      2, 64,  2, 34,  5, 64,128,  8,130, 16, 32, 24,  0,  5,  1,130,
     64, 88,  0,  4,129,144, 41,  1,160,100,  0, 34, 64,  1,162,  0,
     24,  4, 13,  0,  0, 96,128,148, 96,130, 16, 13,128, 48, 12, 18,
     32,  0,  0, 18, 64,192, 32, 33, 88,  2, 65, 16,128, 68,  3,  2,
      4, 19,144, 41,  8,  0, 68,192,  0, 33,  0, 38,  0, 26,128,  1,
     19, 20, 32, 10, 20, 32,  0, 50, 97,  8,  0, 64, 66, 32,  9,128,
      6,  1,129,128, 96, 66,  0,104,144,130,  8, 66,128,  4,  2,128,
      9, 11,  4,  0,152,  0, 12,129,  6, 68, 72,132, 40,  3,146,  0,
      1,128, 64, 10,  0, 12,129,  2,  8, 81,  4, 40,144,  2, 32,  9,
     16, 96,  0,  0,  9,129,160, 12,  0,164,  9,  0,  2, 40,128, 32,
      0,  2,  2,  4,129, 20,  4,  0,  4,  9, 17, 18, 96, 64, 32,  1,
     72, 48, 64, 17,  0,  8, 10,134,  0,  0,  4, 96,129,  4,  1,208,
      2, 65, 24,144,  0, 10, 32,  0,193,  6,  1,  8,128,100,202, 16,
      4,153,128, 72,  1,130, 32, 80,144, 72,128,132, 32,144, 34,  0,
     25,  0,  4, 24, 32, 36, 16,134, 64,194,  0, 36, 18, 16, 68,  0,
     22,  8, 16, 36,  0, 18,  6,  1,  8,144,  0, 18,  2, 77, 16,128,
     64, 80, 34,  0, 67, 16,  1,  0, 48, 33, 10,  0,  0,  1, 20,  0,
     16,132,  4,193, 16, 41, 10,  0,  1,138,  0, 32,  1, 18, 12, 73,
     32,  4,129,  0, 72,  1,  4, 96,128, 18, 12,  8, 16, 72, 74,  4,
     40, 16,  0, 40, 64,132, 69, 80, 16, 96, 16,  6, 68,  1,128,  9,
      0,134,  1, 66,160,  0,144,  0,  5,144, 34, 64, 65,  0,  8,128,
      2,  8,192,  0,  1, 88, 48, 73,  9, 20,  0, 65,  2, 12,  2,128,
     64,137,  0, 36,  8, 16,  5,144, 50, 64, 10,130,  8,  0, 18, 97,
      0,  4, 33,  0, 34,  4, 16, 36,  8, 10,  4,  1, 16,  0, 32, 64,
    132,  4,136, 34, 32,144, 18,  0, 83,  6, 36,  1,  4, 64, 11, 20,
     96,130,  2, 13, 16,144, 12,  8, 32,  9,  0, 20,  9,128,128, 36,
    130,  0, 64,  1,  2, 68,  1, 32, 12, 64,132, 64, 10, 16, 65,  0,
     48,  5,  9,128, 68,  8, 32, 32,  2,  0, 73, 67, 32, 33,  0, 32,
      0,  1,182,  8, 64,  4,  8,  2,128,  1, 65,128, 64,  8, 16, 36,
      0, 32,  4, 18,134,  9,192, 18, 33,129, 20,  4,  0,  2, 32,137,
    180, 68, 18,128,  0,209,  0,105, 64,128,  0, 66, 18,  0, 24,  4,
      0, 73,  6, 33,  2,  4, 40,  2,132,  1,192, 16,104,  0, 32,  8,
     64,  0,  8,145, 16,  1,129, 36,  4,210, 16, 76,136,134,  0, 16,
    128, 12,  2, 20,  0,138,144, 64, 24, 32, 33,128,164,  0, 88, 36,
     32, 16, 16, 96,193, 48, 65, 72,  2, 72,  9,  0, 64,  9,  2,  5,
     17,130, 32, 74, 32, 36, 24,  2, 12, 16, 34, 12, 10,  4,  0,  3,
      6, 72, 72,  4,  4,  2,  0, 33,128,132,  0, 24,  0, 12,  2, 18,
      1,  0, 20,  5,130, 16, 65,137, 18,  8, 64,164, 33,  1,132, 72,
      2, 16, 96, 64,  2, 40,  0, 20,  8, 64,160, 32, 81, 18,  0,194,
      0,  1, 26, 48, 64,137, 18, 76,  2,128,  0,  0, 20,  1,  1,160,
     33, 24, 34, 33, 24,  6, 64,  1,128,  0,144,  4, 72,  2, 48,  4,
      8,  0,  5,136, 36,  8, 72,  4, 36,  2,  6,  0,128,  0,  0,  0,
     16,101, 17,144,  0, 10,130,  4,195,  4, 96, 72, 36,  4,146,  2,
     68,136,128, 64, 24,  6, 41,128, 16,  1,  0,  0, 68,200, 16, 33,
    137, 48,  0, 75,160,  1, 16, 20,  0,  2,148, 64,  0, 32,101,  0,
    162, 12, 64, 34, 32,129, 18, 32,130,  4,  1, 16,  0,  8,136,  0,
      0, 17,128,  4, 66,128, 64, 65, 20,  0, 64, 50, 44,128, 36,  4,
     25,  0,  0,145,  0, 32,131,  0,  5, 64, 32,  9,  1,132, 64, 64,
     32, 32, 17,  0, 64, 65,144, 32,  0,  0, 64,144,146, 72, 24,  6,
      8,129,128, 72,  1, 52, 36, 16, 32,  4,  0, 32,  4, 24,  6, 45,
    144, 16,  1,  0,144,  0, 10, 34,  1,  0, 34,  0, 17,132,  1,  1,
      0, 32,136,  0, 68,  0, 34,  1,  0,166, 64,  2,  6, 32, 17,  0,
      1,200,160,  4,138,  0, 40, 25,128,  0, 82,160, 36, 18, 18,  9,
      8, 36,  1, 72,  0,  4,  0, 36, 64,  2,132,  8,  0,  4, 72, 64,
    144, 96, 10, 34,  1,136, 20,  8,  1,  2,  8,211,  0, 32,192,144,
     36, 16,  0,  0,  1,176,  8, 10,160,  0,128,  0,  1,  9,  0, 32,
     82,  2, 37,  0, 36,  4,  2,132, 36, 16,146, 64,  2,160, 64,  0,
     34,  8, 17,  4,  8,  1, 34,  0, 66, 20,  0,  9,144, 33,  0, 48,
    108,  0,  0, 12,  0, 34,  9,144, 16, 40, 64,  0, 32,192, 32,  0,
    144,  0, 64,  1,130,  5, 18, 18,  9,193,  4, 97,128,  2, 40,129,
     36,  0, 73,  4,  8, 16,134, 41, 65,128, 33, 10, 48, 73,136,144,
      0, 65,  4, 41,129,128, 65,  9,  0, 64, 18, 16, 64,  0, 16, 64,
     72,  2,  5,128,  2, 33, 64, 32,  0, 88, 32, 96,  0,144, 72,  0,
    128, 40,192,128, 72,  0,  0, 68,128,  2,  0,  9,  6,  0, 18,  2,
      1,  0, 16,  8,131, 16, 69, 18,  0, 44,  8,  4, 68,  0, 32, 32,
    192, 16, 32,  1,  0,  5,200, 32,  4,152, 16,  8, 16,  0, 36,  2,
     22, 64,136,  0, 97,136, 18, 36,128,166,  0, 66,  0,  8, 16,  6,
     72, 64,160,  0, 80, 32,  4,129,164, 64, 24,  0,  8, 16,128,  1
};

/*
 * odd primes < 2^16
 *
 * This table is useful to walk thru 16 bit odd primes to factor a 32 bit
 * value.  Use the pr_map[] array to quickly determine if a 16 bit odd
 * value is prime.
 *
 * We end the list with the value 1.  Thus, loops of the form:
 *
 *	FULL isqr, n;
 *	unsigned short *tp;
 *
 *	for (isqr=fsqrt(n), tp=prime; (*tp <= isqr) && (n % *tp); ++tp) {
 *	}
 *
 * will terminate because *tp == 1 and thus (n % *tp) == 0.  To determine if
 * a factor was found, one must:
 *
 *	if (*tp <= isqr && *tp != 1) {
 *		*tp is a factor of n
 *	}
 */
CONST unsigned short prime[MAP_POPCNT+1] = {
    3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
    79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
    163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
    241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
    337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
    431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
    521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
    617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709,
    719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821,
    823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919,
    929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019,
    1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093,
    1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187,
    1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
    1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367,
    1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
    1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543,
    1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613,
    1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709,
    1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801,
    1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901,
    1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999,
    2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087,
    2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179,
    2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281,
    2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371,
    2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
    2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557,
    2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671,
    2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731,
    2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833,