C# 4.0 大數(shù)的運(yùn)算--BigInteger的應(yīng)用詳解

更新時間：2013年05月13日 16:52:21 作者：

本篇文章是對C# 4.0 大數(shù)的運(yùn)算 BigInteger的應(yīng)用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

前段時間，有個同事說

“30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000001”
是個質(zhì)數(shù)。
直覺告訴我，光是在中間加幾個0，在后面加個1，估計(jì)不是質(zhì)數(shù)。
有很多面試題，都會要面試者去做一些關(guān)于大數(shù)的運(yùn)算，例如在這里就有判斷上面這個數(shù)是不是質(zhì)數(shù)的情況。

很明顯，Integer ，Long都是不能來處理如此巨大的數(shù)的。
在.net framework 4.0中，System.Numerics.dll 中提供了BigInteger 類。使用這個類可以很方便的解決這個問題。
判斷n是質(zhì)數(shù)的方法：
1：如果是偶數(shù)，肯定不是質(zhì)數(shù)
2：如果能夠被小于或等于Sqrt(n) 的數(shù)除盡，則不是質(zhì)數(shù)。
代碼如下：

復(fù)制代碼代碼如下:

private static bool IsPrime()
{
    string largeNumber = @"30000000000000000000000...000000001”;
    BigInteger bigInteger = BigInteger.Parse(largeNumber);
    if (bigInteger.IsEven)
    {
        return false;
    }
    for (BigInteger bi = 3; BigInteger.Pow(bi, 2) <= bigInteger; bi += 2)
    {
        if (bigInteger % bi == 0)
        {
            return false;
        }
    }
    return true;
}

本來for 循環(huán)中的代碼應(yīng)該是

復(fù)制代碼代碼如下:

for (BigInteger bi = 3; bi <= BigInteger.Sqrt(bigInteger); bi += 2)
{
    if (bigInteger % bi == 0)
    {
        return false;
    }
}

可惜的是BigInteger 不支持Sqrt方法，所以換用

for (BigInteger bi = 3; BigInteger.Pow(bi, 2) <= bigInteger; bi += 2)

結(jié)果如下圖：

可以知道”30000000000000000000000000…………………………..1”不是質(zhì)數(shù)，可以被13除盡。

2：C語言中有道經(jīng)典的題目是求100！后面有幾個0.

如果你不知道BigInteger的話，應(yīng)該怎么做？

100! 可以理解為

因?yàn)榕紨?shù)比5要多，所以i值比j值多很多，所以求100！有多少個0，可以認(rèn)為是求j的值

當(dāng)然也可以用公式

Sum = [100/5]+[100/(5^2)]+[100/(5^3)]=20+4+0=24;

如果你既沒有思路，也沒有公式，腦子里面只有一個念頭：1*2*3*4*5*..*100 的for循環(huán)，然后統(tǒng)計(jì)0的數(shù)量的話，在4.0 中也可以實(shí)現(xiàn)，雖然好像速度慢了點(diǎn)，不過也還是可以得到答案的：

代碼如下：

統(tǒng)計(jì)的代碼如下：

運(yùn)行結(jié)果如下：

復(fù)制代碼代碼如下:

int count = 0;
for (int i = strSum.Length - 1; i >= 0; i--)
{
    if (strSum[i] == '0')
    {
        count++;
    }
    else
    {
        break;
    }
}