写一个网站,培训网站网站建设,wordpress完整替换网址,网站建设维护 知乎标题是一个测试题。在看到这道题的时候#xff0c;第一反应这是一道考程序复杂度的题#xff0c;其次再是算法问题。 我们先来看看质数的规则: Link#xff1a;http://en.wikipedia.org/wiki/Prime_number C#求质数代码#xff1a; 1 public bool primeNumber(int …标题是一个测试题。在看到这道题的时候第一反应这是一道考程序复杂度的题其次再是算法问题。 我们先来看看质数的规则: Linkhttp://en.wikipedia.org/wiki/Prime_number C#求质数代码 1 public bool primeNumber(int n){
2 int sqr Convert.ToInt32(Math.Sqrt(n));
3 for (int i sqr; i 2; i--){
4 if (n % i 0){
5 b false;
6 }
7 }
8 return b;
9 } 显然以上代码的程序复杂度为N 我们来优化下代码再来看下面代码 1 public bool primeNumber(int n)2 {3 bool b true;4 if (n 2)5 b true;6 else7 {8 int sqr Convert.ToInt32(Math.Sqrt(n));9 for (int i sqr; i 2; i--)
10 {
11 if (n % i 0)
12 {
13 b false;
14 }
15 }
16 }
17 return b;
18 } 通过增加初步判断使程序复杂度降为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# 代码 1 public bool IsProbablePrime(BigInteger source) {2 int certainty 2;3 if (source 2 || source 3)4 return true;5 if (source 2 || source % 2 0)6 return false;7 8 BigInteger d source - 1;9 int s 0;
10
11 while (d % 2 0) {
12 d / 2;
13 s 1;
14 }
15
16 RandomNumberGenerator rng RandomNumberGenerator.Create();
17 byte[] bytes new byte[source.ToByteArray().LongLength];
18 BigInteger a;
19
20 for (int i 0; i certainty; i) {
21 do {
22 rng.GetBytes(bytes);
23 a new BigInteger(bytes);
24 }
25 while (a 2 || a source - 2);
26
27 BigInteger x BigInteger.ModPow(a, d, source);
28 if (x 1 || x source - 1)
29 continue;
30
31 for (int r 1; r s; r) {
32 x BigInteger.ModPow(x, 2, source);
33 if (x 1)
34 return false;
35 if (x source - 1)
36 break;
37 }
38
39 if (x ! source - 1)
40 return false;
41 }
42
43 return true;
44 } 以上是我对本题的解题答案欢迎大家讨论和提供更优办法。 代码戳files.cnblogs.com/tmywu/PrimeNumberProject.zip 转载于:https://www.cnblogs.com/tmywu/archive/2013/05/15/3079403.html
