001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2002, 2003 S�ren Bak
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019: package com.uwyn.rife.pcj.hash;
020:
021: import com.uwyn.rife.pcj.util.Exceptions;
022:
023: /**
024: * This class provides a static table of int sized prime numbers.
025: * For small numbers (0-511) it contains all primes. For larger
026: * numbers it contains 32 primes each time the number of bits is
027: * increased. I.e., there are 32 primes from 512 to 1023,
028: * 32 primes from 1024 to 2048, etc., the primes thus becoming less
029: * dense with size. Within the interval formed by using one more
030: * bit (say, v0 to v1), the 32 primes are formed by searching for
031: * the first prime greater than or equal to v0 + n*(v1-v0)/32, n
032: * belonging to {0,1,2, ..., 31}. This creates a reasonable
033: * distribution.
034: *
035: * @author Søren Bak
036: * @version 1.2 21-08-2003 20:21
037: * @since 1.0
038: */
039: public class Primes {
040:
041: /** Prime numbers in ascending order. */
042: private static final int[] primes = { 1, 3, 5, 7, 11, 13, 17, 19,
043: 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
044: 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
045: 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
046: 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
047: 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353,
048: 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
049: 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
050: 503, 509, 521, 541, 547, 563, 577, 593, 613, 631, 641, 659,
051: 673, 691, 709, 727, 739, 757, 769, 787, 809, 821, 839, 853,
052: 877, 881, 907, 919, 929, 947, 967, 977, 997, 1009, 1031,
053: 1061, 1091, 1123, 1153, 1187, 1217, 1249, 1283, 1319, 1361,
054: 1381, 1409, 1447, 1481, 1511, 1543, 1571, 1601, 1637, 1667,
055: 1697, 1733, 1777, 1801, 1831, 1861, 1889, 1931, 1973, 1987,
056: 2017, 2053, 2113, 2179, 2243, 2309, 2371, 2437, 2503, 2579,
057: 2633, 2689, 2753, 2819, 2887, 2953, 3011, 3079, 3137, 3203,
058: 3271, 3329, 3407, 3457, 3527, 3593, 3659, 3719, 3779, 3847,
059: 3907, 3989, 4049, 4099, 4229, 4357, 4481, 4621, 4751, 4871,
060: 4993, 5147, 5261, 5381, 5507, 5639, 5779, 5897, 6029, 6151,
061: 6277, 6421, 6529, 6659, 6791, 6917, 7043, 7177, 7297, 7433,
062: 7559, 7681, 7817, 7937, 8069, 8209, 8461, 8707, 8963, 9221,
063: 9473, 9733, 10007, 10243, 10499, 10753, 11027, 11273,
064: 11527, 11777, 12037, 12289, 12547, 12809, 13063, 13313,
065: 13577, 13829, 14081, 14341, 14593, 14851, 15107, 15361,
066: 15619, 15877, 16139, 16411, 16901, 17417, 17921, 18433,
067: 18947, 19457, 19973, 20483, 21001, 21517, 22027, 22531,
068: 23041, 23557, 24071, 24593, 25097, 25601, 26113, 26627,
069: 27143, 27653, 28163, 28687, 29191, 29717, 30211, 30727,
070: 31237, 31751, 32257, 32771, 33797, 34819, 35851, 36871,
071: 37889, 38917, 39937, 40961, 41999, 43013, 44041, 45061,
072: 46091, 47111, 48131, 49157, 50177, 51203, 52237, 53267,
073: 54277, 55313, 56333, 57347, 58369, 59393, 60427, 61441,
074: 62467, 63493, 64513, 65537, 67589, 69653, 71693, 73751,
075: 75781, 77839, 79873, 81929, 83969, 86017, 88069, 90121,
076: 92173, 94219, 96259, 98317, 100357, 102407, 104459, 106501,
077: 108553, 110597, 112643, 114689, 116741, 118787, 120833,
078: 122887, 124951, 126989, 129037, 131101, 135173, 139267,
079: 143387, 147457, 151553, 155653, 159763, 163841, 167953,
080: 172049, 176129, 180233, 184321, 188417, 192529, 196613,
081: 200713, 204803, 208907, 212999, 217111, 221197, 225287,
082: 229393, 233477, 237571, 241667, 245771, 249857, 253969,
083: 258061, 262147, 270337, 278543, 286721, 294919, 303119,
084: 311299, 319489, 327689, 335879, 344083, 352267, 360457,
085: 368647, 376837, 385027, 393241, 401411, 409609, 417793,
086: 425987, 434179, 442397, 450563, 458789, 466951, 475141,
087: 483337, 491527, 499717, 507907, 516127, 524309, 540677,
088: 557057, 573451, 589829, 606223, 622603, 638977, 655373,
089: 671753, 688133, 704521, 720899, 737281, 753677, 770053,
090: 786433, 802829, 819229, 835591, 851971, 868369, 884743,
091: 901133, 917513, 933893, 950281, 966659, 983063, 999431,
092: 1015813, 1032193, 1048583, 1081351, 1114117, 1146881,
093: 1179649, 1212427, 1245187, 1277957, 1310723, 1343491,
094: 1376257, 1409027, 1441807, 1474579, 1507369, 1540109,
095: 1572869, 1605677, 1638431, 1671191, 1703941, 1736711,
096: 1769473, 1802261, 1835017, 1867783, 1900553, 1933331,
097: 1966123, 1998881, 2031671, 2064389, 2097169, 2162717,
098: 2228243, 2293771, 2359303, 2424833, 2490377, 2555911,
099: 2621447, 2686979, 2752513, 2818103, 2883593, 2949137,
100: 3014659, 3080237, 3145739, 3211279, 3276803, 3342341,
101: 3407881, 3473419, 3538949, 3604481, 3670027, 3735553,
102: 3801097, 3866627, 3932167, 3997723, 4063237, 4128781,
103: 4194319, 4325389, 4456451, 4587533, 4718617, 4849687,
104: 4980749, 5111833, 5242883, 5373971, 5505037, 5636123,
105: 5767169, 5898253, 6029329, 6160391, 6291469, 6422531,
106: 6553621, 6684673, 6815749, 6946817, 7077893, 7208977,
107: 7340033, 7471127, 7602187, 7733251, 7864331, 7995397,
108: 8126473, 8257537, 8388617, 8650753, 8912921, 9175057,
109: 9437189, 9699331, 9961487, 10223617, 10485767, 10747921,
110: 11010059, 11272193, 11534351, 11796503, 12058679, 12320773,
111: 12582917, 12845069, 13107229, 13369399, 13631489, 13893637,
112: 14155777, 14417927, 14680067, 14942209, 15204391, 15466499,
113: 15728681, 15990791, 16252967, 16515073, 16777259, 17301517,
114: 17825803, 18350093, 18874379, 19398727, 19922993, 20447239,
115: 20971529, 21495809, 22020127, 22544387, 23068673, 23592967,
116: 24117257, 24641543, 25165843, 25690121, 26214401, 26738717,
117: 27262997, 27787267, 28311553, 28835857, 29360147, 29884417,
118: 30408713, 30933011, 31457287, 31981583, 32505901, 33030163,
119: 33554467, 34603013, 35651593, 36700201, 37748743, 38797379,
120: 39845899, 40894481, 41943049, 42991621, 44040253, 45088781,
121: 46137359, 47185967, 48234517, 49283083, 50331653, 51380233,
122: 52428841, 53477453, 54525979, 55574567, 56623153, 57671683,
123: 58720267, 59768843, 60817411, 61865989, 62914619, 63963149,
124: 65011717, 66060311, 67108879, 69206017, 71303171, 73400329,
125: 75497479, 77594641, 79691779, 81788929, 83886091, 85983239,
126: 88080389, 90177541, 92274737, 94371863, 96469001, 98566147,
127: 100663319, 102760453, 104857601, 106954759, 109051907,
128: 111149057, 113246209, 115343383, 117440551, 119537689,
129: 121634819, 123731977, 125829139, 127926307, 130023431,
130: 132120577, 134217757, 138412033, 142606357, 146800649,
131: 150994979, 155189249, 159383563, 163577857, 167772161,
132: 171966481, 176160779, 180355079, 184549429, 188743691,
133: 192937991, 197132293, 201326611, 205520911, 209715263,
134: 213909511, 218103811, 222298127, 226492433, 230686721,
135: 234881033, 239075351, 243269639, 247463939, 251658263,
136: 255852593, 260046883, 264241223, 268435459, 276824071,
137: 285212677, 293601283, 301989917, 310378501, 318767107,
138: 327155743, 335544323, 343932959, 352321547, 360710167,
139: 369098771, 377487361, 385876021, 394264613, 402653189,
140: 411041831, 419430419, 427819031, 436207619, 444596227,
141: 452984849, 461373449, 469762049, 478150661, 486539323,
142: 494927929, 503316511, 511705091, 520093703, 528482347,
143: 536870923, 553648171, 570425377, 587202571, 603979799,
144: 620757019, 637534277, 654311459, 671088667, 687865859,
145: 704643083, 721420307, 738197549, 754974721, 771751961,
146: 788529191, 805306457, 822083597, 838860817, 855638023,
147: 872415239, 889192471, 905969671, 922746883, 939524129,
148: 956301317, 973078537, 989855747, 1006632983, 1023410207,
149: 1040187403, 1056964619, 1073741827, 1107296257, 1140850699,
150: 1174405129, 1207959559, 1241514007, 1275068423, 1308622877,
151: 1342177283, 1375731737, 1409286161, 1442840579, 1476395029,
152: 1509949451, 1543503881, 1577058331, 1610612741, 1644167233,
153: 1677721631, 1711276033, 1744830469, 1778384921, 1811939329,
154: 1845493777, 1879048201, 1912602647, 1946157079, 1979711497,
155: 2013265921, 2046820357, 2080374797, 2113929217,
156: Integer.MAX_VALUE, };
157:
158: /** Prevents instantiation. */
159: private Primes() {
160: }
161:
162: /**
163: * Returns from a static prime table the least prime that is greater
164: * than or equal to a specified value.
165: *
166: * On average, the returned prime will about 1/64 of 2<sup>(r+1)</sup> - 2<sup>r</sup>
167: * greater than n, where r is the order of n (the number of bits
168: * required for representing it).
169: *
170: * @return the least prime in the table that is greater
171: * than or equal to the specified value.
172: */
173: public static int nextPrime(int n) {
174: if (n <= 0)
175: Exceptions.negativeArgument("lower bound", String
176: .valueOf(n));
177: int idx = java.util.Arrays.binarySearch(primes, n);
178: if (idx < 0)
179: return primes[-idx - 1];
180: return primes[idx];
181: }
182:
183: }
|