1
0

PrimeNumberHelper.cs 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
  1. /*
  2. * Copyright (c) Contributors, http://opensimulator.org/
  3. * See CONTRIBUTORS.TXT for a full list of copyright holders.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. * * Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * * Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. * * Neither the name of the OpenSimulator Project nor the
  13. * names of its contributors may be used to endorse or promote products
  14. * derived from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
  17. * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19. * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
  20. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. using System;
  28. namespace OpenSim.Framework
  29. {
  30. /// <summary>
  31. /// Utility class that is used to find small prime numbers and test is number prime number.
  32. /// </summary>
  33. public static class PrimeNumberHelper
  34. {
  35. /// <summary>
  36. /// Precalculated prime numbers.
  37. /// </summary>
  38. private static readonly int[] Primes = new int[]
  39. {
  40. 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239,
  41. 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333,
  42. 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
  43. 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431,
  44. 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449,
  45. 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
  46. 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559,
  47. 5999471, 7199369
  48. };
  49. /// <summary>
  50. /// Get prime number that is equal or larger than <see cref="min"/>.
  51. /// </summary>
  52. /// <param name="min">
  53. /// Minimal returned prime number.
  54. /// </param>
  55. /// <returns>
  56. /// Primer number that is equal or larger than <see cref="min"/>. If <see cref="min"/> is too large, return -1.
  57. /// </returns>
  58. public static int GetPrime(int min)
  59. {
  60. if (min <= 2)
  61. return 2;
  62. if (Primes[ Primes.Length - 1 ] < min)
  63. {
  64. for (int i = min | 1 ; i < 0x7FFFFFFF ; i += 2)
  65. {
  66. if (IsPrime(i))
  67. return i;
  68. }
  69. return -1;
  70. }
  71. for (int i = Primes.Length - 2 ; i >= 0 ; i--)
  72. {
  73. if (min == Primes[ i ])
  74. return min;
  75. if (min > Primes[ i ])
  76. return Primes[ i + 1 ];
  77. }
  78. return 2;
  79. }
  80. /// <summary>
  81. /// Just basic Sieve of Eratosthenes prime number test.
  82. /// </summary>
  83. /// <param name="candinate">
  84. /// Number that is tested.
  85. /// </param>
  86. /// <returns>
  87. /// true, if <see cref="candinate"/> is prime number; otherwise false.
  88. /// </returns>
  89. public static bool IsPrime(int candinate)
  90. {
  91. if ((candinate & 1) == 0)
  92. // Even number - only prime if 2
  93. return candinate == 2;
  94. int upperBound = (int) Math.Sqrt(candinate);
  95. for (int i = 3 ; i < upperBound ; i += 2)
  96. {
  97. if (candinate % i == 0)
  98. return false;
  99. }
  100. return true;
  101. }
  102. }
  103. }