標(biāo)題是一個測試題。在看到這道題的時候，第一反應(yīng)這是一道考程序復(fù)雜度的題，其次再是算法問題。

我們先來看看質(zhì)數(shù)的規(guī)則:

Link：http://en.wikipedia.org/wiki/Prime_number

C#求質(zhì)數(shù)代碼：

1 public bool primeNumber(int n){ 2 int sqr = Convert.ToInt32(Math.Sqrt(n)); 3 for (int i = sqr; i > 2; i--){ 4 if (n % i == 0){ 5 b = false; 6 } 7 } 8 return b; 9 }

顯然以上代碼的程序復(fù)雜度為N

我們來優(yōu)化下代碼，再來看下面代碼：

1 public bool primeNumber(int n) 2 { 3 bool b = true; 4 if (n == 2) 5 b = true; 6 else 7 { 8 int sqr = Convert.ToInt32(Math.Sqrt(n)); 9 for (int i = sqr; i > 2; i--) 10 { 11 if (n % i == 0) 12 { 13 b = false; 14 } 15 } 16 } 17 return b; 18 }

通過增加初步判斷使程序復(fù)雜度降為N/2。

以上兩段代碼判斷大數(shù)是否質(zhì)數(shù)的正確率是100%，但是對于題干

　　1.滿足大數(shù)判斷；

　　2.要求以最快速度得到正確結(jié)果；

顯然是不滿足的。上網(wǎng)查了下最快算法得到準(zhǔn)確結(jié)果，公認(rèn)的一個解決方案是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)確的，但是對于本題來說算是一個基本的解題辦法了。

Miller-Rabin C# 代碼：

1 public bool IsProbablePrime(BigInteger source) { 2 int certainty = 2; 3 if (source == 2 || source == 3) 4 return true; 5 if (source < 2 || source % 2 == 0) 6 return false; 7 8 BigInteger d = source - 1; 9 int s = 0; 10 11 while (d % 2 == 0) { 12 d /= 2; 13 s += 1; 14 } 15 16 RandomNumberGenerator rng = RandomNumberGenerator.Create(); 17 byte[] bytes = new byte[source.ToByteArray().LongLength]; 18 BigInteger a; 19 20 for (int i = 0; i < certainty; i++) { 21 do { 22 rng.GetBytes(bytes); 23 a = new BigInteger(bytes); 24 } 25 while (a < 2 || a >= source - 2); 26 27 BigInteger x = BigInteger.ModPow(a, d, source); 28 if (x == 1 || x == source - 1) 29 continue; 30 31 for (int r = 1; r < s; r++) { 32 x = BigInteger.ModPow(x, 2, source); 33 if (x == 1) 34 return false; 35 if (x == source - 1) 36 break; 37 } 38 39 if (x != source - 1) 40 return false; 41 } 42 43 return true; 44 }

以上是我對本題的解題答案，歡迎大家討論和提供更優(yōu)辦法。

代碼戳：files.cnblogs.com/tmywu/PrimeNumberProject.zip

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/tmywu/archive/2013/05/15/3079403.html

總結(jié)

以上是生活随笔為你收集整理的C# 判断给定大数是否为质数，目标以快速度得到正确的计算结果。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。