服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 使用C# 判断给定大数是否为质数的详解

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

2020-11-29 14:07C#教程网 C/C++

本篇文章是对使用C#判断给定大数是否为质数的方法进行了详细的分析介绍,需要的朋友参考下

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/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03