Use c-sharp to determine whether a given large number is prime or not
- 2020-04-01 23:36:57
- OfStack
C# determines whether a given large number is prime.
When you see this problem, the first reaction is that this is a problem of program complexity, and then the algorithm problem.
Let's first look at the rules for primes:
Link:http://en.wikipedia.org/wiki/Prime_number
C# prime code:
Obviously, the program complexity of the above code is N
Let's optimize the code and look at the following code:
Reduce the program complexity to N/2 by increasing the initial judgment.
The above two pieces of code can determine whether a large number is prime or not 100% of the time, but for the problem
1. Satisfy the judgment of large Numbers;
2. To get the right result as soon as possible;
Obviously not satisfied. The net looked up the fastest algorithm to get accurate results, a recognized solution is the miller-rabin algorithm
Link:http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
The basic principle of miller-rabin is to increase the speed (that is, probability hit) through the judgment method of random number algorithm, but at the expense of accuracy.
Miller-rabin's judgment of the primes of large Numbers is not always accurate, but it is a basic solution for this problem.
Miller-rabin C# code:
When you see this problem, the first reaction is that this is a problem of program complexity, and then the algorithm problem.
Let's first look at the rules for primes:
Link:http://en.wikipedia.org/wiki/Prime_number
C# prime code:
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;
}
Obviously, the program complexity of the above code is N
Let's optimize the code and look at the following code:
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;
}
Reduce the program complexity to N/2 by increasing the initial judgment.
The above two pieces of code can determine whether a large number is prime or not 100% of the time, but for the problem
1. Satisfy the judgment of large Numbers;
2. To get the right result as soon as possible;
Obviously not satisfied. The net looked up the fastest algorithm to get accurate results, a recognized solution is the miller-rabin algorithm
Link:http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
The basic principle of miller-rabin is to increase the speed (that is, probability hit) through the judgment method of random number algorithm, but at the expense of accuracy.
Miller-rabin's judgment of the primes of large Numbers is not always accurate, but it is a basic solution for this problem.
Miller-rabin C# code:
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;
}