| #include "os.h" | |
| ulong smallprimes[1000] = { | |
| 2, | |
| 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, | |
| 2837, | |
| 2843, | |
| 2851, | |
| 2857, | |
| 2861, | |
| 2879, | |
| 2887, | |
| 2897, | |
| 2903, | |
| 2909, | |
| 2917, | |
| 2927, | |
| 2939, | |
| 2953, | |
| 2957, | |
| 2963, | |
| 2969, | |
| 2971, | |
| 2999, | |
| 3001, | |
| 3011, | |
| 3019, | |
| 3023, | |
| 3037, | |
| 3041, | |
| 3049, | |
| 3061, | |
| 3067, | |
| 3079, | |
| 3083, | |
| 3089, | |
| 3109, | |
| 3119, | |
| 3121, | |
| 3137, | |
| 3163, | |
| 3167, | |
| 3169, | |
| 3181, | |
| 3187, | |
| 3191, | |
| 3203, | |
| 3209, | |
| 3217, | |
| 3221, | |
| 3229, | |
| 3251, | |
| 3253, | |
| 3257, | |
| 3259, | |
| 3271, | |
| 3299, | |
| 3301, | |
| 3307, | |
| 3313, | |
| 3319, | |
| 3323, | |
| 3329, | |
| 3331, | |
| 3343, | |
| 3347, | |
| 3359, | |
| 3361, | |
| 3371, | |
| 3373, | |
| 3389, | |
| 3391, | |
| 3407, | |
| 3413, | |
| 3433, | |
| 3449, | |
| 3457, | |
| 3461, | |
| 3463, | |
| 3467, | |
| 3469, | |
| 3491, | |
| 3499, | |
| 3511, | |
| 3517, | |
| 3527, | |
| 3529, | |
| 3533, | |
| 3539, | |
| 3541, | |
| 3547, | |
| 3557, | |
| 3559, | |
| 3571, | |
| 3581, | |
| 3583, | |
| 3593, | |
| 3607, | |
| 3613, | |
| 3617, | |
| 3623, | |
| 3631, | |
| 3637, | |
| 3643, | |
| 3659, | |
| 3671, | |
| 3673, | |
| 3677, | |
| 3691, | |
| 3697, | |
| 3701, | |
| 3709, | |
| 3719, | |
| 3727, | |
| 3733, | |
| 3739, | |
| 3761, | |
| 3767, | |
| 3769, | |
| 3779, | |
| 3793, | |
| 3797, | |
| 3803, | |
| 3821, | |
| 3823, | |
| 3833, | |
| 3847, | |
| 3851, | |
| 3853, | |
| 3863, | |
| 3877, | |
| 3881, | |
| 3889, | |
| 3907, | |
| 3911, | |
| 3917, | |
| 3919, | |
| 3923, | |
| 3929, | |
| 3931, | |
| 3943, | |
| 3947, | |
| 3967, | |
| 3989, | |
| 4001, | |
| 4003, | |
| 4007, | |
| 4013, | |
| 4019, | |
| 4021, | |
| 4027, | |
| 4049, | |
| 4051, | |
| 4057, | |
| 4073, | |
| 4079, | |
| 4091, | |
| 4093, | |
| 4099, | |
| 4111, | |
| 4127, | |
| 4129, | |
| 4133, | |
| 4139, | |
| 4153, | |
| 4157, | |
| 4159, | |
| 4177, | |
| 4201, | |
| 4211, | |
| 4217, | |
| 4219, | |
| 4229, | |
| 4231, | |
| 4241, | |
| 4243, | |
| 4253, | |
| 4259, | |
| 4261, | |
| 4271, | |
| 4273, | |
| 4283, | |
| 4289, | |
| 4297, | |
| 4327, | |
| 4337, | |
| 4339, | |
| 4349, | |
| 4357, | |
| 4363, | |
| 4373, | |
| 4391, | |
| 4397, | |
| 4409, | |
| 4421, | |
| 4423, | |
| 4441, | |
| 4447, | |
| 4451, | |
| 4457, | |
| 4463, | |
| 4481, | |
| 4483, | |
| 4493, | |
| 4507, | |
| 4513, | |
| 4517, | |
| 4519, | |
| 4523, | |
| 4547, | |
| 4549, | |
| 4561, | |
| 4567, | |
| 4583, | |
| 4591, | |
| 4597, | |
| 4603, | |
| 4621, | |
| 4637, | |
| 4639, | |
| 4643, | |
| 4649, | |
| 4651, | |
| 4657, | |
| 4663, | |
| 4673, | |
| 4679, | |
| 4691, | |
| 4703, | |
| 4721, | |
| 4723, | |
| 4729, | |
| 4733, | |
| 4751, | |
| 4759, | |
| 4783, | |
| 4787, | |
| 4789, | |
| 4793, | |
| 4799, | |
| 4801, | |
| 4813, | |
| 4817, | |
| 4831, | |
| 4861, | |
| 4871, | |
| 4877, | |
| 4889, | |
| 4903, | |
| 4909, | |
| 4919, | |
| 4931, | |
| 4933, | |
| 4937, | |
| 4943, | |
| 4951, | |
| 4957, | |
| 4967, | |
| 4969, | |
| 4973, | |
| 4987, | |
| 4993, | |
| 4999, | |
| 5003, | |
| 5009, | |
| 5011, | |
| 5021, | |
| 5023, | |
| 5039, | |
| 5051, | |
| 5059, | |
| 5077, | |
| 5081, | |
| 5087, | |
| 5099, | |
| 5101, | |
| 5107, | |
| 5113, | |
| 5119, | |
| 5147, | |
| 5153, | |
| 5167, | |
| 5171, | |
| 5179, | |
| 5189, | |
| 5197, | |
| 5209, | |
| 5227, | |
| 5231, | |
| 5233, | |
| 5237, | |
| 5261, | |
| 5273, | |
| 5279, | |
| 5281, | |
| 5297, | |
| 5303, | |
| 5309, | |
| 5323, | |
| 5333, | |
| 5347, | |
| 5351, | |
| 5381, | |
| 5387, | |
| 5393, | |
| 5399, | |
| 5407, | |
| 5413, | |
| 5417, | |
| 5419, | |
| 5431, | |
| 5437, | |
| 5441, | |
| 5443, | |
| 5449, | |
| 5471, | |
| 5477, | |
| 5479, | |
| 5483, | |
| 5501, | |
| 5503, | |
| 5507, | |
| 5519, | |
| 5521, | |
| 5527, | |
| 5531, | |
| 5557, | |
| 5563, | |
| 5569, | |
| 5573, | |
| 5581, | |
| 5591, | |
| 5623, | |
| 5639, | |
| 5641, | |
| 5647, | |
| 5651, | |
| 5653, | |
| 5657, | |
| 5659, | |
| 5669, | |
| 5683, | |
| 5689, | |
| 5693, | |
| 5701, | |
| 5711, | |
| 5717, | |
| 5737, | |
| 5741, | |
| 5743, | |
| 5749, | |
| 5779, | |
| 5783, | |
| 5791, | |
| 5801, | |
| 5807, | |
| 5813, | |
| 5821, | |
| 5827, | |
| 5839, | |
| 5843, | |
| 5849, | |
| 5851, | |
| 5857, | |
| 5861, | |
| 5867, | |
| 5869, | |
| 5879, | |
| 5881, | |
| 5897, | |
| 5903, | |
| 5923, | |
| 5927, | |
| 5939, | |
| 5953, | |
| 5981, | |
| 5987, | |
| 6007, | |
| 6011, | |
| 6029, | |
| 6037, | |
| 6043, | |
| 6047, | |
| 6053, | |
| 6067, | |
| 6073, | |
| 6079, | |
| 6089, | |
| 6091, | |
| 6101, | |
| 6113, | |
| 6121, | |
| 6131, | |
| 6133, | |
| 6143, | |
| 6151, | |
| 6163, | |
| 6173, | |
| 6197, | |
| 6199, | |
| 6203, | |
| 6211, | |
| 6217, | |
| 6221, | |
| 6229, | |
| 6247, | |
| 6257, | |
| 6263, | |
| 6269, | |
| 6271, | |
| 6277, | |
| 6287, | |
| 6299, | |
| 6301, | |
| 6311, | |
| 6317, | |
| 6323, | |
| 6329, | |
| 6337, | |
| 6343, | |
| 6353, | |
| 6359, | |
| 6361, | |
| 6367, | |
| 6373, | |
| 6379, | |
| 6389, | |
| 6397, | |
| 6421, | |
| 6427, | |
| 6449, | |
| 6451, | |
| 6469, | |
| 6473, | |
| 6481, | |
| 6491, | |
| 6521, | |
| 6529, | |
| 6547, | |
| 6551, | |
| 6553, | |
| 6563, | |
| 6569, | |
| 6571, | |
| 6577, | |
| 6581, | |
| 6599, | |
| 6607, | |
| 6619, | |
| 6637, | |
| 6653, | |
| 6659, | |
| 6661, | |
| 6673, | |
| 6679, | |
| 6689, | |
| 6691, | |
| 6701, | |
| 6703, | |
| 6709, | |
| 6719, | |
| 6733, | |
| 6737, | |
| 6761, | |
| 6763, | |
| 6779, | |
| 6781, | |
| 6791, | |
| 6793, | |
| 6803, | |
| 6823, | |
| 6827, | |
| 6829, | |
| 6833, | |
| 6841, | |
| 6857, | |
| 6863, | |
| 6869, | |
| 6871, | |
| 6883, | |
| 6899, | |
| 6907, | |
| 6911, | |
| 6917, | |
| 6947, | |
| 6949, | |
| 6959, | |
| 6961, | |
| 6967, | |
| 6971, | |
| 6977, | |
| 6983, | |
| 6991, | |
| 6997, | |
| 7001, | |
| 7013, | |
| 7019, | |
| 7027, | |
| 7039, | |
| 7043, | |
| 7057, | |
| 7069, | |
| 7079, | |
| 7103, | |
| 7109, | |
| 7121, | |
| 7127, | |
| 7129, | |
| 7151, | |
| 7159, | |
| 7177, | |
| 7187, | |
| 7193, | |
| 7207, | |
| 7211, | |
| 7213, | |
| 7219, | |
| 7229, | |
| 7237, | |
| 7243, | |
| 7247, | |
| 7253, | |
| 7283, | |
| 7297, | |
| 7307, | |
| 7309, | |
| 7321, | |
| 7331, | |
| 7333, | |
| 7349, | |
| 7351, | |
| 7369, | |
| 7393, | |
| 7411, | |
| 7417, | |
| 7433, | |
| 7451, | |
| 7457, | |
| 7459, | |
| 7477, | |
| 7481, | |
| 7487, | |
| 7489, | |
| 7499, | |
| 7507, | |
| 7517, | |
| 7523, | |
| 7529, | |
| 7537, | |
| 7541, | |
| 7547, | |
| 7549, | |
| 7559, | |
| 7561, | |
| 7573, | |
| 7577, | |
| 7583, | |
| 7589, | |
| 7591, | |
| 7603, | |
| 7607, | |
| 7621, | |
| 7639, | |
| 7643, | |
| 7649, | |
| 7669, | |
| 7673, | |
| 7681, | |
| 7687, | |
| 7691, | |
| 7699, | |
| 7703, | |
| 7717, | |
| 7723, | |
| 7727, | |
| 7741, | |
| 7753, | |
| 7757, | |
| 7759, | |
| 7789, | |
| 7793, | |
| 7817, | |
| 7823, | |
| 7829, | |
| 7841, | |
| 7853, | |
| 7867, | |
| 7873, | |
| 7877, | |
| 7879, | |
| 7883, | |
| 7901, | |
| 7907, | |
| 7919, | |
| }; |