我实现了一种不同的质数检查方法，原因如下：
- 大多数解决方案都会在同一个倍数上进行不必要的迭代（例如，它们会检查5、10，然后是15，而单个% 5将测试这些内容）。
- % 2将处理所有偶数（所有以0、2、4、6或8结尾的整数）。
- % 5将处理所有5的倍数（所有以5结尾的整数）。
- 剩下的就是测试以1、3、7或9结尾的整数的偶数除法。但美妙之处在于我们可以每次增加10，而不是每次增加2，我将演示一种线程化的解决方案。
- 其他算法没有线程化，所以它们不能像我希望的那样充分利用您的核心。
- 我还需要支持非常大的质数，因此我需要使用BigInteger数据类型，而不是int、long等。
这是我的实现：
public static BigInteger IntegerSquareRoot(BigInteger value)
{
if (value > 0)
{
int bitLength = value.ToByteArray().Length * 8;
BigInteger root = BigInteger.One << (bitLength / 2);
while (!IsSquareRoot(value, root))
{
root += value / root;
root /= 2;
}
return root;
}
else return 0;
}
private static Boolean IsSquareRoot(BigInteger n, BigInteger root)
{
BigInteger lowerBound = root * root;
BigInteger upperBound = (root + 1) * (root + 1);
return (n >= lowerBound && n < upperBound);
}
static bool IsPrime(BigInteger value)
{
Console.WriteLine("Checking if {0} is a prime number.", value);
if (value < 3)
{
if (value == 2)
{
Console.WriteLine("{0} is a prime number.", value);
return true;
}
else
{
Console.WriteLine("{0} is not a prime number because it is below 2.", value);
return false;
}
}
else
{
if (value % 2 == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by 2.", value);
return false;
}
else if (value == 5)
{
Console.WriteLine("{0} is a prime number.", value);
return true;
}
else if (value % 5 == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by 5.", value);
return false;
}
else
{
AutoResetEvent success = new AutoResetEvent(false);
AutoResetEvent failure = new AutoResetEvent(false);
AutoResetEvent onesSucceeded = new AutoResetEvent(false);
AutoResetEvent threesSucceeded = new AutoResetEvent(false);
AutoResetEvent sevensSucceeded = new AutoResetEvent(false);
AutoResetEvent ninesSucceeded = new AutoResetEvent(false);
BigInteger squareRootedValue = IntegerSquareRoot(value);
Thread ones = new Thread(() =>
{
for (BigInteger i = 11; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
onesSucceeded.Set();
});
ones.Start();
Thread threes = new Thread(() =>
{
for (BigInteger i = 3; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
threesSucceeded.Set();
});
threes.Start();
Thread sevens = new Thread(() =>
{
for (BigInteger i = 7; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
sevensSucceeded.Set();
});
sevens.Start();
Thread nines = new Thread(() =>
{
for (BigInteger i = 9; i <= squareRootedValue; i += 10)
{
if (value % i == 0)
{
Console.WriteLine("{0} is not a prime number because it is divisible by {1}.", value, i);
failure.Set();
}
}
ninesSucceeded.Set();
});
nines.Start();
Thread successWaiter = new Thread(() =>
{
AutoResetEvent.WaitAll(new WaitHandle[] { onesSucceeded, threesSucceeded, sevensSucceeded, ninesSucceeded });
success.Set();
});
successWaiter.Start();
int result = AutoResetEvent.WaitAny(new WaitHandle[] { success, failure });
try
{
successWaiter.Abort();
}
catch { }
try
{
ones.Abort();
}
catch { }
try
{
threes.Abort();
}
catch { }
try
{
sevens.Abort();
}
catch { }
try
{
nines.Abort();
}
catch { }
if (result == 1)
{
return false;
}
else
{
Console.WriteLine("{0} is a prime number.", value);
return true;
}
}
}
}
更新：如果你想更快地使用试除法实现方案，你可以考虑使用质数缓存。
一个数字只有在它不被小于它平方根的其他质数整除时才是质数。此外，如果你处理的是足够大的值（从 Rosetta Code 中获取，以防该网站关闭），你可以考虑使用
Miller-Rabin素性检验的概率版本来检查数字的质数性：
public static class BigIntegerExtensions
{
public static bool IsProbablePrime(this BigInteger source, int certainty)
{
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;
}
}
a的起始值设为 3，并将其递增 2 而不是 1（并将 2 是质数的情况视为特例）。但请参考这里：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes。 - Matthew Watsonsqrt(n)以获取需要进行试除法的素数，则筛选比通过复合数进行不必要的除法更加繁琐，如果避免2、3和可能是5的倍数，那么您就是一个企业家。 如果您筛选到n来查找sieve中是否为素数，则您的算法渐近更差（并且常数因子也不会让其在小数字方面获胜）。 - Daniel Fischer