Mega Code Archive

 

Categories / Java / Development Class

 

Returns from a static prime table the least prime that is greater than or equal to a specified value

/*  * @(#)$Id: Primes.java 3619 2008-03-26 07:23:03Z yui $  *  * Copyright 2006-2008 Makoto YUI  *  * Licensed under the Apache License, Version 2.0 (the "License");  * you may not use this file except in compliance with the License.  * You may obtain a copy of the License at  *  *     http://www.apache.org/licenses/LICENSE-2.0  *  * Unless required by applicable law or agreed to in writing, software  * distributed under the License is distributed on an "AS IS" BASIS,  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  * See the License for the specific language governing permissions and  * limitations under the License.  *   * Contributors:  *     Makoto YUI - initial implementation  */ //package xbird.util.math; import java.util.Arrays; /**  *   * <DIV lang="en"></DIV>  * <DIV lang="ja"></DIV>  *   * @author Makoto YUI (yuin405+xbird@gmail.com)  */ public final class Primes {     static final int[] PRIMES = { 3, 5, 7, 13, 19, 31, 43, 61, 73, 89, 103, 109, 139, 151, 181,             193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 601, 619, 661, 823,             859, 883, 1021, 1063, 1093, 1153, 1231, 1321, 1429, 1489, 1621, 1699, 1789, 1873, 1951,             2029, 2131, 2143, 2311, 2383, 2593, 2731, 2803, 3001, 3121, 3259, 3391, 3583, 3673,             3919, 4093, 4273, 4423, 4651, 4801, 5023, 5281, 5521, 5743, 5881, 6301, 6571, 6871,             7129, 7489, 7759, 8089, 8539, 8863, 9283, 9721, 10141, 10531, 11071, 11551, 12073,             12613, 13009, 13759, 14323, 14869, 15649, 16363, 17029, 17839, 18541, 19471, 20233,             21193, 22159, 23059, 24181, 25171, 26263, 27541, 28753, 30013, 31321, 32719, 34213,             35731, 37309, 38923, 40639, 42463, 44281, 46309, 48313, 50461, 52711, 55051, 57529,             60091, 62299, 65521, 68281, 71413, 74611, 77713, 81373, 84979, 88663, 92671, 96739,             100801, 105529, 109849, 115021, 120079, 125509, 131011, 136861, 142873, 149251, 155863,             162751, 169891, 177433, 185071, 193381, 202129, 211063, 220021, 229981, 240349, 250969,             262111, 273643, 285841, 298411, 311713, 325543, 339841, 355009, 370663, 386989, 404269,             422113, 440809, 460081, 480463, 501829, 524221, 547399, 571603, 596929, 623353, 651019,             679909, 709741, 741343, 774133, 808441, 844201, 881539, 920743, 961531, 1004119,             1048573, 1094923, 1143283, 1193911, 1246963, 1302181, 1359733, 1420039, 1482853,             1548541, 1616899, 1688413, 1763431, 1841293, 1922773, 2008081, 2097133, 2189989,             2286883, 2388163, 2493853, 2604013, 2719669, 2840041, 2965603, 3097123, 3234241,             3377191, 3526933, 3682363, 3845983, 4016041, 4193803, 4379719, 4573873, 4776223,             4987891, 5208523, 5439223, 5680153, 5931313, 6194191, 6468463, 6754879, 7053331,             7366069, 7692343, 8032639, 8388451, 8759953, 9147661, 9552733, 9975193, 10417291,             10878619, 11360203, 11863153, 12387841, 12936529, 13509343, 14107801, 14732413,             15384673, 16065559, 16777141, 17519893, 18295633, 19105483, 19951231, 20834689,             21757291, 22720591, 23726449, 24776953, 25873963, 27018853, 28215619, 29464579,             30769093, 32131711, 33554011, 35039911, 36591211, 38211163, 39903121, 41669479,             43514521, 45441199, 47452879, 49553941, 51747991, 54039079, 56431513, 58930021,             61539091, 64263571, 67108669, 70079959, 73182409, 76422793, 79806229, 83339383,             87029053, 90881083, 94906249, 99108043, 103495879, 108077731, 112863013, 117860053,             123078019, 128526943, 134217439, 140159911, 146365159, 152845393, 159612601, 166679173,             174058849, 181765093, 189812341, 198216103, 206991601, 216156043, 225726379, 235720159,             246156271, 257054491, 268435009, 280319203, 292730833, 305691181, 319225021, 333358513,             348117151, 363529759, 379624279, 396432481, 413983771, 432312511, 451452613, 471440161,             492312523, 514109251, 536870839, 560640001, 585461743, 611382451, 638450569, 666717199,             696235363, 727060069, 759249643, 792864871, 827967631, 864625033, 902905501, 942880663,             984625531, 1028218189, 1073741719, 1121280091, 1170923713, 1222764841, 1276901371,             1333434301, 1392470281, 1454120779, 1518500173, 1585729993, 1655935399, 1729249999,             1805811253, 1885761133, 1969251079, 2056437379, 2147482951, Integer.MAX_VALUE };     /**      * Returns from a static prime table the least prime that is greater       * than or equal to a specified value.      */     public static int findLeastPrimeNumber(int n) {         assert (n >= 0) : n;         int idx = Arrays.binarySearch(PRIMES, n);         if(idx < 0) {             idx = -idx - 1;             if(idx >= PRIMES.length) {                 idx = PRIMES.length - 1;             }             return PRIMES[idx]; // if not found, use max prime (in this case 9973).         }         return PRIMES[idx];     } }