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

来源：南昌达内IT教育培训学校时间：2022/6/26 17:16:12

　　C#判断给定大数是否为质数，目标以度得到正确的计算结果。

　　在看到这道题的时候，第 一反应这是一道考程序复杂度的题，其次再是算法问题。

　　C#求质数代码：

　　复制代码 代码如下:

　　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;

　　}

　　显然以上代码的程序复杂度为N

　　我们来优化下代码，再来看下面代码：

　　复制代码 代码如下:

　　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;

　　}

　　通过增加初步判断使程序复杂度降为N/2。

　　以上两段代码判断大数是否质数的正确率是，但是对于题干

　　1.满足大数判断;

　　2.要求以较度得到正确结果;

　　显然是不满足的。上网查了下较快算法得到准确结果，公认的一个解决方案是Miller-Rabin算法

　　Link:http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

　　Miller-Rabin 基本原理是通过随机数算法判断的方式提高速度(即概率击中)，但是牺牲的是准确率。

　　Miller-Rabin 对输入大数的质数判断的结果并不一定是完全准确的，但是对于本题来说算是一个基本的解题办法了。

　　Miller-Rabin C# 代码：

　　复制代码 代码如下:

　　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;

　　}

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/1810/news/540743/违者必究！ 以上就是南昌达内IT教育培训学校 小编为您整理 使用C# 判断给定大数是否为质数的详解的全部内容。