#include #include #include /* * We process blocks of 2*3*5*7*11=2310 numbers. There can be up to * 1*2*4*6*10=480 primes in each such block, so we pack these into 15 32-bit * words. Maximum memory use is therefore ceil(n/2310)*60 bytes, or * approximately 111 MB for numbers up to 2^32. */ static const unsigned int initial[] = { 2, 3, 5, 7, 11 }; static const uint32_t offsets[][32] = { { 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, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229, 233, 239, 241, 247, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293, 299, 307, 311 }, { 313, 317, 323, 331, 337, 347, 349, 353, 359, 361, 367, 373, 377, 379, 383, 389, 391, 397, 401, 403, 409, 419, 421, 431, 433, 437, 439, 443, 449, 457, 461, 463 }, { 467, 479, 481, 487, 491, 493, 499, 503, 509, 521, 523, 527, 529, 533, 541, 547, 551, 557, 559, 563, 569, 571, 577, 587, 589, 593, 599, 601, 607, 611, 613, 617 }, { 619, 629, 631, 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 689, 691, 697, 701, 703, 709, 713, 719, 727, 731, 733, 739, 743, 751, 757, 761, 767, 769, 773 }, { 779, 787, 793, 797, 799, 809, 811, 817, 821, 823, 827, 829, 839, 841, 851, 853, 857, 859, 863, 871, 877, 881, 883, 887, 893, 899, 901, 907, 911, 919, 923, 929 }, { 937, 941, 943, 947, 949, 953, 961, 967, 971, 977, 983, 989, 991, 997, 1003, 1007, 1009, 1013, 1019, 1021, 1027, 1031, 1033, 1037, 1039, 1049, 1051, 1061, 1063, 1069, 1073, 1079 }, { 1081, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1121, 1123, 1129, 1139, 1147, 1151, 1153, 1157, 1159, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1207, 1213, 1217, 1219, 1223, 1229, 1231, 1237 }, { 1241, 1247, 1249, 1259, 1261, 1271, 1273, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1313, 1319, 1321, 1327, 1333, 1339, 1343, 1349, 1357, 1361, 1363, 1367, 1369, 1373, 1381, 1387 }, { 1391, 1399, 1403, 1409, 1411, 1417, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1457, 1459, 1469, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1501, 1511, 1513, 1517, 1523, 1531, 1537, 1541 }, { 1543, 1549, 1553, 1559, 1567, 1571, 1577, 1579, 1583, 1591, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1633, 1637, 1643, 1649, 1651, 1657, 1663, 1667, 1669, 1679, 1681, 1691, 1693, 1697 }, { 1699, 1703, 1709, 1711, 1717, 1721, 1723, 1733, 1739, 1741, 1747, 1751, 1753, 1759, 1763, 1769, 1777, 1781, 1783, 1787, 1789, 1801, 1807, 1811, 1817, 1819, 1823, 1829, 1831, 1843, 1847, 1849 }, { 1853, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1891, 1901, 1907, 1909, 1913, 1919, 1921, 1927, 1931, 1933, 1937, 1943, 1949, 1951, 1957, 1961, 1963, 1973, 1979, 1987, 1993, 1997, 1999, 2003 }, { 2011, 2017, 2021, 2027, 2029, 2033, 2039, 2041, 2047, 2053, 2059, 2063, 2069, 2071, 2077, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2117, 2119, 2129, 2131, 2137, 2141, 2143, 2147, 2153, 2159 }, { 2161, 2171, 2173, 2179, 2183, 2197, 2201, 2203, 2207, 2209, 2213, 2221, 2227, 2231, 2237, 2239, 2243, 2249, 2251, 2257, 2263, 2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297, 2309, 2311 } }; static const uint32_t jumps[] = { 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 2, 4, 6, 2, 10, 2, 4, 2, 12, 10, 2, 4, 2, 4, 6, 2, 6, 4, 6, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 6, 8, 6, 10, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 10, 2, 10, 2, 4, 2, 4, 6, 8, 4, 2, 4, 12, 2, 6, 4, 2, 6, 4, 6, 12, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 10, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 6, 6, 2, 6, 6, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 6, 4, 8, 6, 4, 6, 2, 4, 6, 8, 6, 4, 2, 10, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 8, 6, 4, 2, 4, 6, 6, 2, 6, 4, 8, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 6, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10, 2, 6, 4, 6, 2, 6, 4, 2, 4, 6, 6, 8, 4, 2, 6, 10, 8, 4, 2, 4, 2, 4, 8, 10, 6, 2, 4, 8, 6, 6, 4, 2, 4, 6, 2, 6, 4, 6, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 6, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 8, 4, 6, 2, 6, 6, 4, 2, 4, 6, 8, 4, 2, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 10, 2, 4, 6, 8, 6, 4, 2, 6, 4, 6, 8, 4, 6, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 6, 6, 2, 6, 6, 4, 2, 10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 10, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 12, 6, 4, 6, 2, 4, 6, 2, 12, 4, 2, 4, 8, 6, 4, 2, 4, 2, 10, 2, 10, 6, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 10, 6, 8, 6, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 6, 4, 6, 2, 6, 4, 2, 4, 2, 10, 12, 2, 4, 2, 10, 2, 6, 4, 2, 4, 6, 6, 2, 10, 2, 6, 4, 14, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 12 }; static const int reverse[] = { 0, -1, -1, -1, 1, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, 4, -1, 5, -1, -1, -1, -1, -1, 6, -1, -1, -1, 7, -1, 8, -1, -1, -1, 9, -1, -1, -1, -1, -1, 10, -1, -1, -1, -1, -1, 11, -1, 12, -1, -1, -1, -1, -1, 13, -1, -1, -1, 14, -1, 15, -1, -1, -1, -1, -1, 16, -1, -1, -1, 17, -1, -1, -1, -1, -1, 18, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, 20, -1, 21, -1, -1, -1, 22, -1, 23, -1, -1, -1, 24, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 25, -1, -1, -1, 26, -1, -1, -1, -1, -1, 27, -1, 28, -1, -1, -1, -1, -1, -1, -1, -1, -1, 29, -1, 30, -1, -1, -1, -1, -1, 31, -1, -1, -1, -1, -1, 32, -1, -1, -1, 33, -1, 34, -1, -1, -1, 35, -1, -1, -1, -1, -1, 36, -1, 37, -1, -1, -1, -1, -1, -1, -1, -1, -1, 38, -1, 39, -1, -1, -1, 40, -1, 41, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 42, -1, -1, -1, -1, -1, -1, -1, -1, -1, 43, -1, 44, -1, -1, -1, 45, -1, 46, -1, -1, -1, 47, -1, -1, -1, -1, -1, 48, -1, 49, -1, -1, -1, -1, -1, 50, -1, -1, -1, 51, -1, -1, -1, -1, -1, 52, -1, -1, -1, -1, -1, 53, -1, -1, -1, -1, -1, 54, -1, 55, -1, -1, -1, -1, -1, 56, -1, -1, -1, 57, -1, 58, -1, -1, -1, -1, -1, 59, -1, -1, -1, 60, -1, -1, -1, -1, -1, 61, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, -1, 63, -1, 64, -1, -1, -1, 65, -1, -1, -1, -1, -1, 66, -1, -1, -1, -1, -1, -1, -1, 67, -1, -1, -1, -1, -1, 68, -1, -1, -1, -1, -1, -1, -1, -1, -1, 69, -1, 70, -1, -1, -1, 71, -1, -1, -1, -1, -1, 72, -1, 73, -1, -1, -1, -1, -1, 74, -1, -1, -1, -1, -1, 75, -1, -1, -1, 76, -1, 77, -1, -1, -1, 78, -1, -1, -1, -1, -1, 79, -1, 80, -1, -1, -1, -1, -1, 81, -1, -1, -1, 82, -1, 83, -1, -1, -1, -1, -1, 84, -1, -1, -1, -1, -1, -1, -1, -1, -1, 85, -1, 86, -1, -1, -1, -1, -1, -1, -1, -1, -1, 87, -1, 88, -1, -1, -1, 89, -1, 90, -1, -1, -1, 91, -1, -1, -1, -1, -1, 92, -1, -1, -1, -1, -1, -1, -1, 93, -1, -1, -1, 94, -1, 95, -1, -1, -1, 96, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 97, -1, 98, -1, -1, -1, -1, -1, 99, -1, -1, -1, 100, -1, 101, -1, -1, -1, -1, -1, 102, -1, -1, -1, 103, -1, -1, -1, -1, -1, 104, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 105, -1, 106, -1, -1, -1, 107, -1, 108, -1, -1, -1, 109, -1, -1, -1, -1, -1, -1, -1, 110, -1, -1, -1, -1, -1, 111, -1, -1, -1, 112, -1, -1, -1, -1, -1, 113, -1, 114, -1, -1, -1, 115, -1, -1, -1, -1, -1, 116, -1, 117, -1, -1, -1, -1, -1, 118, -1, -1, -1, -1, -1, -1, -1, -1, -1, 119, -1, 120, -1, -1, -1, 121, -1, -1, -1, -1, -1, 122, -1, 123, -1, -1, -1, -1, -1, 124, -1, -1, -1, 125, -1, 126, -1, -1, -1, 127, -1, 128, -1, -1, -1, -1, -1, -1, -1, -1, -1, 129, -1, 130, -1, -1, -1, -1, -1, -1, -1, -1, -1, 131, -1, 132, -1, -1, -1, 133, -1, -1, -1, -1, -1, 134, -1, -1, -1, -1, -1, 135, -1, 136, -1, -1, -1, -1, -1, 137, -1, -1, -1, -1, -1, 138, -1, -1, -1, 139, -1, -1, -1, -1, -1, 140, -1, -1, -1, -1, -1, 141, -1, 142, -1, -1, -1, -1, -1, 143, -1, -1, -1, 144, -1, 145, -1, -1, -1, -1, -1, 146, -1, -1, -1, 147, -1, -1, -1, -1, -1, 148, -1, -1, -1, -1, -1, -1, -1, 149, -1, -1, -1, 150, -1, 151, -1, -1, -1, -1, -1, 152, -1, -1, -1, 153, -1, -1, -1, -1, -1, -1, -1, 154, -1, -1, -1, -1, -1, 155, -1, -1, -1, 156, -1, -1, -1, -1, -1, 157, -1, 158, -1, -1, -1, 159, -1, -1, -1, -1, -1, 160, -1, -1, -1, -1, -1, -1, -1, 161, -1, -1, -1, -1, -1, 162, -1, -1, -1, 163, -1, 164, -1, -1, -1, -1, -1, -1, -1, -1, -1, 165, -1, 166, -1, -1, -1, -1, -1, 167, -1, -1, -1, 168, -1, 169, -1, -1, -1, 170, -1, 171, -1, -1, -1, -1, -1, -1, -1, -1, -1, 172, -1, 173, -1, -1, -1, -1, -1, -1, -1, -1, -1, 174, -1, 175, -1, -1, -1, 176, -1, 177, -1, -1, -1, 178, -1, -1, -1, -1, -1, -1, -1, 179, -1, -1, -1, -1, -1, 180, -1, -1, -1, 181, -1, 182, -1, -1, -1, 183, -1, -1, -1, -1, -1, 184, -1, -1, -1, -1, -1, 185, -1, 186, -1, -1, -1, -1, -1, 187, -1, -1, -1, 188, -1, -1, -1, -1, -1, -1, -1, 189, -1, -1, -1, 190, -1, -1, -1, -1, -1, 191, -1, -1, -1, -1, -1, -1, -1, 192, -1, -1, -1, 193, -1, 194, -1, -1, -1, 195, -1, 196, -1, -1, -1, 197, -1, -1, -1, -1, -1, -1, -1, 198, -1, -1, -1, -1, -1, 199, -1, -1, -1, 200, -1, -1, -1, -1, -1, 201, -1, -1, -1, -1, -1, 202, -1, -1, -1, -1, -1, 203, -1, 204, -1, -1, -1, -1, -1, 205, -1, -1, -1, -1, -1, 206, -1, -1, -1, 207, -1, 208, -1, -1, -1, 209, -1, -1, -1, -1, -1, 210, -1, 211, -1, -1, -1, -1, -1, 212, -1, -1, -1, 213, -1, 214, -1, -1, -1, 215, -1, 216, -1, -1, -1, -1, -1, -1, -1, -1, -1, 217, -1, 218, -1, -1, -1, -1, -1, -1, -1, -1, -1, 219, -1, 220, -1, -1, -1, -1, -1, 221, -1, -1, -1, 222, -1, -1, -1, -1, -1, 223, -1, 224, -1, -1, -1, -1, -1, 225, -1, -1, -1, 226, -1, 227, -1, -1, -1, 228, -1, -1, -1, -1, -1, 229, -1, -1, -1, -1, -1, 230, -1, -1, -1, -1, -1, -1, -1, 231, -1, -1, -1, 232, -1, 233, -1, -1, -1, -1, -1, 234, -1, -1, -1, -1, -1, -1, -1, -1, -1, 235, -1, -1, -1, -1, -1, -1, -1, 236, -1, -1, -1, 237, -1, 238, -1, -1, -1, 239, -1, 240, -1, -1, -1, 241, -1, -1, -1, -1, -1, -1, -1, 242, -1, -1, -1, -1, -1, -1, -1, -1, -1, 243, -1, -1, -1, -1, -1, 244, -1, 245, -1, -1, -1, 246, -1, -1, -1, -1, -1, -1, -1, 247, -1, -1, -1, -1, -1, 248, -1, -1, -1, -1, -1, 249, -1, -1, -1, 250, -1, 251, -1, -1, -1, 252, -1, -1, -1, -1, -1, 253, -1, 254, -1, -1, -1, -1, -1, 255, -1, -1, -1, 256, -1, -1, -1, -1, -1, 257, -1, 258, -1, -1, -1, -1, -1, -1, -1, -1, -1, 259, -1, 260, -1, -1, -1, -1, -1, -1, -1, -1, -1, 261, -1, 262, -1, -1, -1, 263, -1, 264, -1, -1, -1, 265, -1, -1, -1, -1, -1, 266, -1, 267, -1, -1, -1, -1, -1, 268, -1, -1, -1, 269, -1, 270, -1, -1, -1, 271, -1, -1, -1, -1, -1, 272, -1, -1, -1, -1, -1, 273, -1, 274, -1, -1, -1, -1, -1, 275, -1, -1, -1, -1, -1, 276, -1, -1, -1, -1, -1, 277, -1, -1, -1, 278, -1, -1, -1, -1, -1, 279, -1, -1, -1, -1, -1, -1, -1, 280, -1, -1, -1, 281, -1, 282, -1, -1, -1, 283, -1, 284, -1, -1, -1, 285, -1, -1, -1, -1, -1, -1, -1, 286, -1, -1, -1, -1, -1, 287, -1, -1, -1, 288, -1, -1, -1, -1, -1, -1, -1, 289, -1, -1, -1, 290, -1, -1, -1, -1, -1, 291, -1, 292, -1, -1, -1, -1, -1, 293, -1, -1, -1, -1, -1, 294, -1, -1, -1, 295, -1, 296, -1, -1, -1, 297, -1, -1, -1, -1, -1, 298, -1, -1, -1, -1, -1, -1, -1, 299, -1, -1, -1, 300, -1, 301, -1, -1, -1, 302, -1, 303, -1, -1, -1, -1, -1, -1, -1, -1, -1, 304, -1, 305, -1, -1, -1, -1, -1, -1, -1, -1, -1, 306, -1, 307, -1, -1, -1, 308, -1, 309, -1, -1, -1, 310, -1, -1, -1, -1, -1, 311, -1, 312, -1, -1, -1, -1, -1, -1, -1, -1, -1, 313, -1, 314, -1, -1, -1, 315, -1, -1, -1, -1, -1, 316, -1, -1, -1, -1, -1, -1, -1, 317, -1, -1, -1, -1, -1, 318, -1, -1, -1, 319, -1, 320, -1, -1, -1, -1, -1, 321, -1, -1, -1, 322, -1, -1, -1, -1, -1, 323, -1, -1, -1, -1, -1, -1, -1, 324, -1, -1, -1, 325, -1, -1, -1, -1, -1, 326, -1, 327, -1, -1, -1, 328, -1, -1, -1, -1, -1, -1, -1, 329, -1, -1, -1, -1, -1, 330, -1, -1, -1, 331, -1, -1, -1, -1, -1, 332, -1, 333, -1, -1, -1, 334, -1, -1, -1, -1, -1, 335, -1, 336, -1, -1, -1, -1, -1, 337, -1, -1, -1, -1, -1, 338, -1, -1, -1, 339, -1, -1, -1, -1, -1, 340, -1, -1, -1, -1, -1, 341, -1, 342, -1, -1, -1, -1, -1, 343, -1, -1, -1, -1, -1, 344, -1, -1, -1, 345, -1, 346, -1, -1, -1, -1, -1, -1, -1, -1, -1, 347, -1, 348, -1, -1, -1, -1, -1, -1, -1, -1, -1, 349, -1, 350, -1, -1, -1, 351, -1, 352, -1, -1, -1, 353, -1, -1, -1, -1, -1, 354, -1, 355, -1, -1, -1, -1, -1, 356, -1, -1, -1, 357, -1, 358, -1, -1, -1, -1, -1, -1, -1, -1, -1, 359, -1, -1, -1, -1, -1, 360, -1, 361, -1, -1, -1, -1, -1, 362, -1, -1, -1, 363, -1, 364, -1, -1, -1, -1, -1, 365, -1, -1, -1, 366, -1, -1, -1, -1, -1, 367, -1, -1, -1, -1, -1, -1, -1, 368, -1, -1, -1, 369, -1, 370, -1, -1, -1, 371, -1, 372, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 373, -1, -1, -1, -1, -1, 374, -1, -1, -1, 375, -1, -1, -1, -1, -1, 376, -1, 377, -1, -1, -1, 378, -1, -1, -1, -1, -1, 379, -1, 380, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 381, -1, -1, -1, 382, -1, 383, -1, -1, -1, 384, -1, -1, -1, -1, -1, -1, -1, 385, -1, -1, -1, -1, -1, 386, -1, -1, -1, 387, -1, 388, -1, -1, -1, 389, -1, 390, -1, -1, -1, -1, -1, -1, -1, -1, -1, 391, -1, 392, -1, -1, -1, -1, -1, -1, -1, -1, -1, 393, -1, -1, -1, -1, -1, 394, -1, 395, -1, -1, -1, 396, -1, -1, -1, -1, -1, 397, -1, 398, -1, -1, -1, -1, -1, 399, -1, -1, -1, 400, -1, 401, -1, -1, -1, 402, -1, -1, -1, -1, -1, 403, -1, -1, -1, -1, -1, 404, -1, 405, -1, -1, -1, -1, -1, 406, -1, -1, -1, 407, -1, 408, -1, -1, -1, -1, -1, -1, -1, -1, -1, 409, -1, -1, -1, -1, -1, 410, -1, -1, -1, -1, -1, -1, -1, 411, -1, -1, -1, -1, -1, 412, -1, -1, -1, 413, -1, 414, -1, -1, -1, 415, -1, -1, -1, -1, -1, -1, -1, 416, -1, -1, -1, -1, -1, 417, -1, -1, -1, 418, -1, -1, -1, -1, -1, 419, -1, 420, -1, -1, -1, 421, -1, -1, -1, -1, -1, 422, -1, 423, -1, -1, -1, -1, -1, 424, -1, -1, -1, -1, -1, 425, -1, -1, -1, -1, -1, 426, -1, -1, -1, 427, -1, -1, -1, -1, -1, 428, -1, 429, -1, -1, -1, -1, -1, 430, -1, -1, -1, 431, -1, 432, -1, -1, -1, 433, -1, 434, -1, -1, -1, -1, -1, -1, -1, -1, -1, 435, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 436, -1, 437, -1, -1, -1, 438, -1, 439, -1, -1, -1, -1, -1, -1, -1, -1, -1, 440, -1, 441, -1, -1, -1, -1, -1, 442, -1, -1, -1, 443, -1, 444, -1, -1, -1, 445, -1, -1, -1, -1, -1, 446, -1, -1, -1, -1, -1, 447, -1, 448, -1, -1, -1, -1, -1, -1, -1, -1, -1, 449, -1, 450, -1, -1, -1, -1, -1, 451, -1, -1, -1, 452, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 453, -1, -1, -1, 454, -1, 455, -1, -1, -1, 456, -1, 457, -1, -1, -1, 458, -1, -1, -1, -1, -1, -1, -1, 459, -1, -1, -1, -1, -1, 460, -1, -1, -1, 461, -1, -1, -1, -1, -1, 462, -1, 463, -1, -1, -1, 464, -1, -1, -1, -1, -1, 465, -1, 466, -1, -1, -1, -1, -1, 467, -1, -1, -1, -1, -1, 468, -1, -1, -1, 469, -1, 470, -1, -1, -1, 471, -1, -1, -1, -1, -1, 472, -1, 473, -1, -1, -1, -1, -1, 474, -1, -1, -1, 475, -1, 476, -1, -1, -1, 477, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 478, -1, 479, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }; static void print_initials(uint32_t limit) { const unsigned int *p; for ( p = initial; p < initial + sizeof initial / sizeof initial[0] && *p <= limit; p++ ) printf("%u\n", *p); } static void print_rest(uint32_t limit) { uint32_t base; uint32_t (*buffer)[15]; uint32_t (*current)[15]; unsigned int word; base = 0; current = buffer = calloc(1 + limit / 2310, sizeof *buffer); while (1) { for (word = 0; word < 15; word++) { uint32_t template = (*current)[word]; uint32_t mask = 1; unsigned int bit; for (bit = 0; bit < 32; bit++, mask <<= 1) { uint32_t number, filter, jump; if (template & mask) continue; number = base + offsets[word][bit]; if (number > limit) goto out; printf("%u\n", number); if (number >= 0x10000) continue; filter = number * number - 13; jump = reverse[(number - 13) % 2310]; while (filter <= limit) { uint32_t fblock = filter / 2310; int fbit = reverse[filter % 2310]; buffer[fblock][fbit >> 5] |= 1 << (fbit & 0x1f); filter += jumps[jump++] * number; if (jump == 480) jump = 0; } } } current++; base += 2310; } out: free(buffer); } int main(int argc, char **argv) { uint32_t limit; if (argc < 2) { fprintf(stderr, "Usage: %s \n", argv[0]); return EXIT_FAILURE; } if (sscanf(argv[1], "%" SCNu32, &limit) != 1) { fprintf(stderr, "%s: bad limit `%s'\n", argv[0], argv[1]); return EXIT_FAILURE; } print_initials(limit); if (limit > initial[sizeof initial / sizeof initial[0] - 1]) print_rest(limit); return EXIT_SUCCESS; }