当前位置：首页 > 资讯 > 技术文档

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

时间：2020-11-25 15:35 编辑：来源：阅读：
扫一扫，手机访问

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

[b]C#判断给定大数是否为质数，目标以快速度得到正确的计算结果。 [/b]在看到这道题的时候，第一反应这是一道考程序复杂度的题，其次再是算法问题。我们先来看看质数的规则: Link：http://en.wikipedia.org/wiki/Prime_number [b]C#求质数代码： [/b]

[u]复制代码[/u] 代码如下:

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 我们来优化下代码，再来看下面代码：

[u]复制代码[/u] 代码如下:

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。以上两段代码判断大数是否质数的正确率是100%，但是对于题干　　1.满足大数判断；　　2.要求以最快速度得到正确结果；显然是不满足的。上网查了下最快算法得到准确结果，公认的一个解决方案是Miller-Rabin算法 Link:http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin 基本原理是通过随机数算法判断的方式提高速度（即概率击中），但是牺牲的是准确率。 Miller-Rabin 对输入大数的质数判断的结果并不一定是完全准确的，但是对于本题来说算是一个基本的解题办法了。 [b]Miller-Rabin C# 代码： [/b]

[u]复制代码[/u] 代码如下:

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;
         }

全部评论(0)

上一篇：C语言中的内存泄露怎样避免与检测
下一篇：浅析C++编程当中的线程

资讯排行榜
更多>>