1 /******************************************************************************* 2 3 @file Primes.d 4 5 Copyright (C) 2004 Kris Bell 6 7 This software is provided 'as-is', without any express or implied 8 warranty. In no event will the authors be held liable for damages 9 of any kind arising from the use of this software. 10 11 Permission is hereby granted to anyone to use this software for any 12 purpose, including commercial applications, and to alter it and/or 13 redistribute it freely, subject to the following restrictions: 14 15 1. The origin of this software must not be misrepresented; you must 16 not claim that you wrote the original software. If you use this 17 software in a product, an acknowledgment within documentation of 18 said product would be appreciated but is not required. 19 20 2. Altered source versions must be plainly marked as such, and must 21 not be misrepresented as being the original software. 22 23 3. This notice may not be removed or altered from any distribution 24 of the source. 25 26 27 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 28 29 30 @version Initial version, April 2004 31 @author Kris 32 33 34 *******************************************************************************/ 35 36 // originally: module primes; 37 module imports.inline2a; 38 39 class Primes 40 { 41 private 42 static const short[] primes = 43 [ 44 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 45 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 46 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 47 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 48 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 49 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 50 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 51 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 52 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 53 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 54 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 55 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 56 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 57 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 58 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 59 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 60 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 61 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 62 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 63 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 64 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 65 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 66 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 67 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 68 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 69 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 70 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 71 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 72 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 73 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 74 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 75 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 76 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 77 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 78 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 79 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 80 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 81 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 82 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 83 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 84 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 85 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 86 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 87 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 88 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 89 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 90 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 91 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 92 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 93 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 94 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 95 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 96 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 97 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 98 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 99 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 100 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 101 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 102 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 103 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 104 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 105 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 106 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 107 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 108 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 109 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 110 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 111 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 112 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 113 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 114 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 115 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 116 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 117 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 118 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 119 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 120 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 121 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 122 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 123 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 124 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 125 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 126 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 127 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 128 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 129 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 130 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 131 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 132 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 133 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 134 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 135 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 136 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 137 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 138 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 139 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 140 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 141 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 142 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 143 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919 144 ]; 145 146 /********************************************************************* 147 148 Binary-chop search on sorted data. 149 150 *********************************************************************/ 151 152 private static ptrdiff_t bsearch (in short[] array, short match) 153 { 154 ptrdiff_t l, u, m; 155 156 l = -1; 157 u = array.length; 158 159 while (l+1 != u) 160 { 161 m = (l + u) / 2; 162 if (array[m] < match) 163 l = m; 164 else 165 u = m; 166 } 167 168 if (u >= array.length || array[u] != match) 169 return -u; 170 return u; 171 } 172 173 /********************************************************************** 174 175 return a prime number between 2 and 7919 (inclusive) that 176 is equal to or larger than the given 'target' number. 177 178 **********************************************************************/ 179 180 static int lookup (short target) 181 { 182 auto index = bsearch (primes, target); 183 if (index < 0) 184 index = -index; 185 186 if (index >= primes.length) 187 index = primes.length - 1; 188 189 return primes[index]; 190 } 191 }