使用C# 判断给定大数是否为质数的详解

判断一个大数是否为质数是一个常见的问题。早期的解决方式是通过试除法，即将该数不断除以比它小的所有正整数，如果在这些正整数中存在约数，那么这个数就不是质数。 但是，这种试除法效率极低，在判断大数时会消耗大量时间和资源。因此，我们需要更快速且高效的方式来判断大数是否为质数。

下面我们将介绍一种使用“Miller-Rabin素性测试算法”的C#代码实现的方法，该算法的效率比试除法高很多。

Miller-Rabin素性测试算法

“Miller-Rabin素性测试算法”是一种使用随机性质的判定质数的方法，能够快速且高效地判断一个数是否为质数。 基本的流程如下：

1. 将原数n-1分解成2^r * d(d是一个奇数)
2. 随机选取b[n-1]∈[2, n-2]之间的整数
3. 求出x=b[n-1]^dmodn，i∈ [0, r-1]
4. 如果x≠1且x≠n-1并且对于任何0≤j≤r-2，都有x^(2^j)d ≡ -1 mod n，则输出n为合数，退出算法
5. 如果以上条件都不满足，则重复2—5步

如果重复k次都没有运行到步骤四，那么输出n为素数。

C# 代码实现

根据上述算法，我们可以使用以下C#代码来判定大数是否为质数。以下代码中，我们将n=147647、k=5（重复测试的次数）作为示例。

using System;
using System.Numerics;

class Program
{
    static void Main(string[] args)
    {
        //示例: 判断147647是否为质数
        BigInteger n = 147647;
        int k = 5;
        bool res = IsPrime(n, k);
        if(res==true)
        {
            Console.WriteLine(n + " is a prime number.");
        }
        else
        {
            Console.WriteLine(n + " is not a prime number.");
        }
    }

    // Miller-Rabin素性测试算法
    static bool IsPrime(BigInteger n, int k)
    {
        // 基本情况: n = 2或3时，是质数
        if (n == 2 || n == 3)
        {
            return true;
        }

        // 偶数，不是质数
        if (n % 2 == 0)
        {
            return false;
        }

        // 把n-1分解成2^r * d的形式
        BigInteger d = n - 1;
        int r = 0;
        while (d % 2 == 0)
        {
            r++;
            d /= 2;
        }

        // 判断n是不是质数
        Random rand = new Random();
        for (int i = 0; i < k; i++)
        {
            BigInteger a = rand.Next(2, n - 1);
            BigInteger x = BigInteger.ModPow(a, d, n);//求出b[n-1]^d mod n

            if (x == 1 || x == n - 1)
            {
                continue;
            }

            int j;
            for (j = 0; j < r - 1; j++)
            {
                x = BigInteger.ModPow(x, 2, n);//这里直接求x^2 mod n
                if (x == n - 1)
                {
                    break;
                }
            }
            if (j == r - 1)
            {
                return false;
            }
        }
        return true;
    }
}

示例说明

1. 判断147647是否为质数

BigInteger n = 147647;
int k = 5;
bool res = IsPrime(n, k);

首先，我们将要判断的大数n赋值为147647，然后设定重复测试的次数为k=5。这里设置重复测试的次数越多，判断结果越可靠，但也相应地会消耗更多的时间和资源。

接着，我们使用IsPrime函数对n进行判定，得到判定结果res。如果res为true，那么说明n是质数，否则说明n不是质数。

1. 判断1000000000000000003是否为质数

BigInteger n = 1000000000000000003;
int k = 5;
bool res = IsPrime(n, k);

接着，我们将要判断的大数n赋值为1000000000000000003，然后设定重复测试的次数为k=5。这里我们测试的数比前一个例子更大。

接着，我们使用IsPrime函数对n进行判定，得到判定结果res。如果res为true，那么说明n是质数，否则说明n不是质数。

总的来说，尽管使用Miller-Rabin算法进行质数判定的效率相较于试除法有了很大的提升，但仍对计算资源要求较高，并且存在概率性问题。但在实际中，它仍是一种非常经典的质数判定算法，可以满足大部分情况的需求。