我实现了一种不同的方法来检查素数，因为：
- 这些解决方案中的大多数都会不必要地重复相同的倍数（例如，它们检查 5、10，然后检查 15，单个 % by 5 将测试的东西）。
- % by 2 将处理所有偶数（所有以 0、2、4、6 或 8 结尾的整数）。
- % by 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
{
// The only way this number is a prime number at this point is if it is divisible by numbers ending with 1, 3, 7, and 9.
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 素性检验的概率版本来检查数字的素性：
// Miller-Rabin primality test as an extension method on the BigInteger type.
// Based on the Ruby implementation on this page.
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;
}
// There is no built-in method for generating random BigInteger values.
// Instead, random BigIntegers are constructed from randomly generated
// byte arrays of the same length as the source.
RandomNumberGenerator rng = RandomNumberGenerator.Create();
byte[] bytes = new byte[source.ToByteArray().LongLength];
BigInteger a;
for(int i = 0; i < certainty; i++)
{
do
{
// This may raise an exception in Mono 2.10.8 and earlier.
// http://bugzilla.xamarin.com/show_bug.cgi?id=2761
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;
}
}
