mcs/class/corlib/System.Collections/HashPrimeNumbers.cs

   1 //
   2 // HashPrimeNumbers.cs
   3 //
   4 // Author:
   5 //   Sergey Chaban (serge@wildwestsoftware.com)
   6 //
   7 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 namespace System.Collections
  30 {
  31         static class HashPrimeNumbers
  32         {
  33                 static readonly int [] primeTbl = {
  34                         11,
  35                         19,
  36                         37,
  37                         73,
  38                         109,
  39                         163,
  40                         251,
  41                         367,
  42                         557,
  43                         823,
  44                         1237,
  45                         1861,
  46                         2777,
  47                         4177,
  48                         6247,
  49                         9371,
  50                         14057,
  51                         21089,
  52                         31627,
  53                         47431,
  54                         71143,
  55                         106721,
  56                         160073,
  57                         240101,
  58                         360163,
  59                         540217,
  60                         810343,
  61                         1215497,
  62                         1823231,
  63                         2734867,
  64                         4102283,
  65                         6153409,
  66                         9230113,
  67                         13845163
  68                 };
  69
  70
  71                 //
  72                 // Private static methods
  73                 //
  74                 public static bool TestPrime (int x)
  75                 {
  76                         if ((x & 1) != 0) {
  77                                 int top = (int)Math.Sqrt (x);
  78
  79                                 for (int n = 3; n < top; n += 2) {
  80                                         if ((x % n) == 0)
  81                                                 return false;
  82                                 }
  83                                 return true;
  84                         }
  85                         // There is only one even prime - 2.
  86                         return (x == 2);
  87                 }
  88
  89                 public static int CalcPrime (int x)
  90                 {
  91                         for (int i = (x & (~1))-1; i< Int32.MaxValue; i += 2) {
  92                                 if (TestPrime (i)) return i;
  93                         }
  94                         return x;
  95                 }
  96
  97                 public static int ToPrime (int x)
  98                 {
  99                         for (int i = 0; i < primeTbl.Length; i++) {
 100                                 if (x <= primeTbl [i])
 101                                         return primeTbl [i];
 102                         }
 103                         return CalcPrime (x);
 104                 }
 105
 106         }
 107 }