- /// <summary>
- /// 素数帮忙类
- /// 本类是从.net源码 类 internal static class HashHelpers 类里抽取相应的代码
- /// https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs,e8668bf19da49963
- /// Hashtable.cs里
- /// </summary>
- public class PrimeHelper {
- /// <summary>
- /// 给定一些素数(除了2)
- /// </summary>
- public static readonly int[] Primes = {
- 3,
- 7,
- 11,
- 17,
- 23,
- 29,
- 37,
- 47,
- 59,
- 71,
- 89,
- 107,
- 131,
- 163,
- 197,
- 239,
- 293,
- 353,
- 431,
- 521,
- 631,
- 761,
- 919,
- 1103,
- 1327,
- 1597,
- 1931,
- 2333,
- 2801,
- 3371,
- 4049,
- 4861,
- 5839,
- 7013,
- 8419,
- 10103,
- 12143,
- 14591,
- 17519,
- 21023,
- 25229,
- 30293,
- 36353,
- 43627,
- 52361,
- 62851,
- 75431,
- 90523,
- 108631,
- 130363,
- 156437,
- 187751,
- 225307,
- 270371,
- 324449,
- 389357,
- 467237,
- 560689,
- 672827,
- 807403,
- 968897,
- 1162687,
- 1395263,
- 1674319,
- 2009191,
- 2411033,
- 2893249,
- 3471899,
- 4166287,
- 4999559,
- 5999471,
- 7199369
- };
- /// <summary>
- /// 判断是否是素数
- /// </summary>
- /// <param name="candidate"></param>
- /// <returns></returns>
- public static bool IsPrime(int candidate) {
- //偶数当然不是素数
- if ((candidate & 1) != 0) {
- int limit = (int) Math.Sqrt(candidate);
- for (int divisor = 3; divisor <= limit; divisor += 2) {
- if ((candidate % divisor) == 0) return false;
- }
- return true;
- }
- //2是素数
- return (candidate == 2);
- }
- /// <summary>
- /// 大于给定数的最小素数
- /// </summary>
- /// <param name="min"></param>
- /// <returns></returns>
- public static int GetPrime(int min) {
- if (min < 0) {
- throw new ArgumentException("给定数必须是自然数");
- }
- //先从给定数组里找
- foreach(int prime in Primes) {
- if (prime >= min) {
- return prime;
- }
- }
- //给定数组里没有相应的素数,则循环找
- //如果min是偶数,则起始值为加1,否则起始值为本身
- for (int i = (min | 1); i < Int32.MaxValue; i += 2) {
- if (IsPrime(i)) return i;
- }
- return min;
- }
- /// <summary>
- /// 获取最小素数(2除外)
- /// </summary>
- /// <returns></returns>
- public static int GetMinPrime() {
- return Primes[0];
- }
- }
来源: http://www.bubuko.com/infodetail-2010173.html