使用C# 判断给定大数是否为质数的详解
更新时间：2020年4月25日 17:47 点击：1456
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;
}
在看到这道题的时候，第一反应这是一道考程序复杂度的题，其次再是算法问题。
我们先来看看质数的规则:
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语言指针的两处小tip分享
下一篇: C语言获得电脑的IP地址的小例子
相关文章
- 我们在使用C#做项目的时候，基本上都需要制作登录界面，那么今天我们就来一步步看看，如果简单的实现登录界面呢，本文给出2个例子，由简入难，希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料，文中示例代码非常详细，供大家参考和学习，感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧，本文通过图文并茂的形式给大家介绍的非常详细，需要的朋友参考下吧...2021-05-17
- 本文主要介绍了C#中new的几种用法，具有很好的参考价值，下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法，帮助大家更好的理解和使用c#，感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现，故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 本文通过例子，讲述了C++调用C#的DLL程序的方法，作出了以下总结，下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门，了解C#最基本的知识点，C#是一种简洁的，类型安全的一种完全面向对象的开发语言，是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言，需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法，需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法，文中代码非常详细，帮助大家更好的参考和学习，感兴趣的朋友可以了解下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25