当前位置:  编程技术>c/c++/嵌入式

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

    来源: 互联网  发布时间:2014-10-14

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

C#判断给定大数是否为质数,目标以快速度得到正确的计算结果。
在看到这道题的时候,第一反应这是一道考程序复杂度的题,其次再是算法问题。
我们先来看看质数的规则:
Link:http://en.wikipedia.org/wiki/Prime_number
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。
以上两段代码判断大数是否质数的正确率是100%,但是对于题干
  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;
         }


    
 
 

您可能感兴趣的文章:

  • c#中SAPI使用总结——SpVoice的使用方法
  • c#友好显示日期 c#日期datetime使用方法
  • 请问在工作岗位的朋友!使用java开发的公司对c#的态度如何?
  • c#自带缓存使用方法 c#移除清理缓存
  • C#中的switch case使用介绍
  • c# 空合并运算符“??”的使用详解
  • 使用C#实现在屏幕上画图效果的代码实例
  • 深入C#中使用SqlDbType.Xml类型参数的使用详解
  • c#闭包使用方法示例
  • c# split分隔字符串使用方法
  • c#的params参数使用示例
  • c#使用资源文件的示例
  • 使用C# Winform应用程序获取网页源文件的解决方法
  • C#将时间转成文件名使用方法
  • C# 使用匿名函数解决EventHandler参数传递的难题
  • 使用C#获取系统特殊文件夹路径的解决方法
  • C#使用带like的sql语句时防sql注入的方法
  • C#可选参数的相关使用
  • C# 静态构造函数使用总结
  • C# WndProc的使用方法示例
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • linux 下大数库 miracl 的使用方法,求高手指教
  • C++ I/O 成员 tellg():使用输入流读取流指针
  • 在测试memset函数的执行效率时,分为使用Cash和不使用Cash辆种方式,该如何控制是否使用缓存?
  • C++ I/O 成员 tellp():使用输出流读取流指针
  • 求ibm6000的中文使用手册 !从来没用过服务器,现在急需使用它,不知如何使用! 急!!!!!
  • Python不使用print而直接输出二进制字符串
  • 请问:在使用oracle数据库作开发时,是使用pro*c作开发好些,还是使用库函数如oci等好一些啊?或者它们有什么区别或者优缺点啊?
  • Office 2010 Module模式下使用VBA Addressof
  • 急求结果!!假设一个有两个元素的信号量集S,表示了一个磁带驱动器系统,其中进程1使用磁带机A,进程2同时使用磁带机A和B,进程3使用磁带机B。
  • windows下tinyxml.dll下载安装使用(c++解析XML库)
  • 使用了QWidget的程序,如何使用后台程序启动它?
  • tcmalloc内存泄露优化c++开源库下载,安装及使用介绍
  • 共享内存一般是怎么使用的,是同消息队列配合使用么
  • sharepoint 2010 使用STSNavigate函数实现文件下载举例
  • Jsp可否使用带有GUI的JavaBean,如何使用?
  • 使用libpcap读取tcpdump抓取的文件并解析c代码实例
  • asp程序使用的access在Linux下如何使用!
  • c/c++预处理命令预#,##使用介绍
  • 新装的Linux使用root用户不能使用FTP?
  • 在div中使用css让文字底部对齐的方法
  • LINUX下使用Eclipse,如何使用交叉编译器?
  • Python namedtuple(命名元组)使用实例
  • redhat9内存使用率高达73%,怎么查看内存具体使用情况


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3