c# 求质数的方法

 1         static bool IsPrime(int num)
 2         {
 3             if (num <= 1) return false;
 4             for (int i = 2; i * i <= num; i++)
 5             {
 6                 if (num % i == 0) return false;
 7             }
 8             return true;
 9         }
10 
11         static int CountPrimes(int n)
12         {
13             int count = 0;
14             for (int i = 2; i < n; i++)
15             {
16                 if (IsPrime(i)) count++;
17             }
18             return count;
19         }            

        static int GetPrimesNum(int maxNum)
        {
            int result = 0;
            var marks = new int[maxNum - 1];
            for (int i = 0; i < maxNum - 1; i++)
            {
                if (marks[i] == 0)
                {
                    result++;
                    int temp = 2;
                    while ((i + 2) * temp <= maxNum)
                    {
                        marks[(i + 2) * temp - 2] = 1;
                        temp++;
                    }
                }
            }
            return result;
        }

米勒-拉宾素数测试法：米勒-拉宾素数测试法是一种基于费马小定理的概率算法，用于测试一个数是否为质数。其基本思想是随机选择一个数a作为底数，然后计算a^(n-1) mod n的值，如果等于1，则该数可能是质数；如果不等于1，则一定不是质数。这个过程可以重复进行多次，每次选择不同的底数a，以提高测试的准确性。这种方法具有高效、准确的特点，但存在一定的概率错误率。

//待续