使用C# 判斷給定大數(shù)是否為質(zhì)數(shù)的詳解

2020-01-26 16:13:40

字體：大中小

供稿：網(wǎng)友

C#判斷給定大數(shù)是否為質(zhì)數(shù)，目標(biāo)以快速度得到正確的計(jì)算結(jié)果。
在看到這道題的時(shí)候，第一反應(yīng)這是一道考程序復(fù)雜度的題，其次再是算法問題。
我們先來看看質(zhì)數(shù)的規(guī)則:
Link：http://en.wikipedia.org/wiki/Prime_number
C#求質(zhì)數(shù)代碼：

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

public bool primeNumber(int n){
             int sqr = Convert.ToInt32(Math.Sqrt(n));
             for (int i = sqr; i > 2; i--){
                 if (n % i == 0){
                     b = false;
                 }
             }
             return b;
         }

顯然以上代碼的程序復(fù)雜度為N
我們來優(yōu)化下代碼，再來看下面代碼：

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

public bool primeNumber(int n)
         {
             bool b = true;
             if (n == 1 || n == 2)
                 b = true;
             else
             {
                 int sqr = Convert.ToInt32(Math.Sqrt(n));
                 for (int i = sqr; i > 2; i--)
                 {
                     if (n % i == 0)
                     {
                         b = false;
                     }
                 }
             }
             return b;
         }

通過增加初步判斷使程序復(fù)雜度降為N/2。
以上兩段代碼判斷大數(shù)是否質(zhì)數(shù)的正確率是100%，但是對于題干
　　1.滿足大數(shù)判斷；
　　2.要求以最快速度得到正確結(jié)果；
顯然是不滿足的。上網(wǎng)查了下最快算法得到準(zhǔn)確結(jié)果，公認(rèn)的一個(gè)解決方案是Miller-Rabin算法
Link:http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
Miller-Rabin 基本原理是通過隨機(jī)數(shù)算法判斷的方式提高速度（即概率擊中），但是犧牲的是準(zhǔn)確率。
Miller-Rabin 對輸入大數(shù)的質(zhì)數(shù)判斷的結(jié)果并不一定是完全準(zhǔn)確的，但是對于本題來說算是一個(gè)基本的解題辦法了。
Miller-Rabin C# 代碼：

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

public bool IsProbablePrime(BigInteger source) {
             int certainty = 2;
             if (source == 2 || source == 3)
                 return true;
             if (source < 2 || source % 2 == 0)
                 return false;

             BigInteger d = source - 1;
             int s = 0;

             while (d % 2 == 0) {
                 d /= 2;
                 s += 1;
             }

             RandomNumberGenerator rng = RandomNumberGenerator.Create();
             byte[] bytes = new byte[source.ToByteArray().LongLength];
             BigInteger a;

             for (int i = 0; i < certainty; i++) {
                 do {
                     rng.GetBytes(bytes);
                     a = new BigInteger(bytes);
                 }
                 while (a < 2 || a >= source - 2);

                 BigInteger x = BigInteger.ModPow(a, d, source);
                 if (x == 1 || x == source - 1)
                     continue;

                 for (int r = 1; r < s; r++) {
                     x = BigInteger.ModPow(x, 2, source);
                     if (x == 1)
                         return false;
                     if (x == source - 1)
                         break;
                 }

                 if (x != source - 1)
                     return false;
             }

             return true;
         }