C# 我如何测试素性？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/627463/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I test for primality?
提问by Oxymoron
I am writing a little library with some prime number related methods. As I've done the groundwork (aka working methods) and now I'm looking for some optimization. Ofcourse the internet is an excellent place to do so. I've, however, stumbled upon a rounding problem and I was wondering how to solve this.
我正在用一些与素数相关的方法编写一个小库。因为我已经完成了基础工作（又名工作方法），现在我正在寻找一些优化。当然，互联网是这样做的绝佳场所。然而，我偶然发现了一个舍入问题，我想知道如何解决这个问题。
In the loop I use to test a number for it's primality it's more efficient to search until sqrt(n) instead of n/2 or even n - 1. But due to rounding problems some number get skipped and thus some primes are skipped! For example, the 10000th prime should be: 104729, but the 'optimized' version ends up with: 103811.
在循环中，我用来测试一个数字的素数，搜索直到 sqrt(n) 而不是 n/2 甚至 n - 1 的效率更高。但是由于舍入问题，一些数字被跳过，因此一些素数被跳过！例如，第 10000 个质数应为：104729，但“优化”版本最终为：103811。
Some code (it's open for more optimization, I know, but I can handle only one thing at a time):
一些代码（我知道它可以进行更多优化，但我一次只能处理一件事）：
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers
if (test == 0 || test == 1) return false;
// 2 and 3 are prime numbers
if (test == 2) return true;
// all even numbers, save 2, are not prime
if (test % 2 == 0) return false;
double squared = Math.Sqrt(test);
int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));
// start with 5, make increments of 2, even numbers do not need to be tested
for (int idx = 3; idx < flooredAndSquared; idx++)
{
if (test % idx == 0)
{
return false;
}
}
return true;
}
I know the squared part fails me (or I fail), tried Math.Ceiling as well, with about the same results.
我知道平方部分失败了（或者我失败了），也尝试了 Math.Ceiling，结果大致相同。
采纳答案by Hosam Aly
Sadly, I haven't tried the algorithmic approaches before. But if you want to implement your approach efficiently, I'd suggest doing some caching. Create an array to store all prime numbers less than a defined threshold, fill this array, and search within/using it.
遗憾的是，我之前没有尝试过算法方法。但是如果你想有效地实施你的方法，我建议做一些缓存。创建一个数组来存储所有小于定义阈值的素数，填充这个数组，并在其中搜索/使用它。
In the following example, finding whether a number is prime is O(1) in the best case (namely, when the number is less than or equal to maxPrime, which is 821,461 for a 64K buffer), and is somewhat optimized for other cases (by checking mod over only 64K numbers out of the first 820,000 -- about 8%).
在下面的示例中，在最佳情况下（即，当该数字小于或等于 时maxPrime，对于 64K 缓冲区为 821,461），确定一个数是否为素数是 O(1 )，并且在其他情况下进行了一些优化（通过在前 820,000 个数字中仅检查 64K 个数字——大约 8%）。
(Note: Don't take this answer as the "optimal" approach. It's more of an example on how to optimize your implementation.)
（注意：不要将此答案视为“最佳”方法。它更多是关于如何优化您的实现的示例。）
public static class PrimeChecker
{
private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB
private static int[] primes;
public static int MaxPrime { get; private set; }
public static bool IsPrime(int value)
{
if (value <= MaxPrime)
{
return Array.BinarySearch(primes, value) >= 0;
}
else
{
return IsPrime(value, primes.Length) && IsLargerPrime(value);
}
}
static PrimeChecker()
{
primes = new int[BufferSize];
primes[0] = 2;
for (int i = 1, x = 3; i < primes.Length; x += 2)
{
if (IsPrime(x, i))
primes[i++] = x;
}
MaxPrime = primes[primes.Length - 1];
}
private static bool IsPrime(int value, int primesLength)
{
for (int i = 0; i < primesLength; ++i)
{
if (value % primes[i] == 0)
return false;
}
return true;
}
private static bool IsLargerPrime(int value)
{
int max = (int)Math.Sqrt(value);
for (int i = MaxPrime + 2; i <= max; i += 2)
{
if (value % i == 0)
return false;
}
return true;
}
}
回答by dirkgently
Try the sieve of eratosthenes-- that should take out getting the root and floating point issues.
As for the floor, you will be better served by taking the ceiling.
至于floor，您将获得更好的服务ceiling。
回答by Chris Ballance
Here is a halfway decent function I wrote to solve one of the Euler:
这是我为解决欧拉问题而编写的一个半途而废的函数：
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
回答by schnaader
I guess this is your problem:
我想这是你的问题：
for (int idx = 3; idx < flooredAndSquared; idx++)
This should be
这应该是
for (int idx = 3; idx <= flooredAndSquared; idx++)
so you don't get square numbers as primes. Also, you can use "idx += 2" instead of "idx++" because you only have to test odd numbers (as you wrote in the comment directly above...).
所以你不会得到平方数作为素数。此外，您可以使用“idx += 2”而不是“idx++”，因为您只需要测试奇数（正如您在上面的评论中所写的那样...）。
回答by Inisheer
Try this...
尝试这个...
if (testVal == 2) return true;
if (testVal % 2 == 0) return false;
for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
if (testVal % i == 0)
return false;
}
return true;
Ive used this quite a few times.. Not as fast as a sieve.. but it works.
我已经用过很多次了..不如筛子快..但它有效。
回答by Guffa
I posted a class that uses the sieve or Eratosthenes to calculate prime numbers here:
我在这里发布了一个使用筛法或 Eratosthenes 计算素数的类：
Is the size of an array constrained by the upper limit of int (2147483647)?
回答by Mark Lavin
I don't know if this is quite what you are looking for but if you are really concerned about speed then you should look into probablistic methods for testing primality rather than using a sieve. Rabin-Milleris a probabilistic primality test used by Mathematica.
我不知道这是否正是您要寻找的，但如果您真的很关心速度，那么您应该研究用于测试素性的概率方法，而不是使用筛子。Rabin-Miller是 Mathematica 使用的概率素性检验。
回答by Samir Talwar
Your for loop should look like this:
您的 for 循环应如下所示：
for (int idx = 3; idx * idx <= test; idx++) { ... }
That way, you avoid floating-point computation. Should run faster and it'll be more accurate. This is why the forstatement conditional is simply a boolean expression: it makes things like this possible.
这样，您就可以避免浮点计算。应该跑得更快，它会更准确。这就是为什么for条件语句只是一个布尔表达式的原因：它使这样的事情成为可能。
回答by James McMahon
You might want to look into Fermat's little theorem.
你可能想看看费马小定理。
Here is the pseudo code from the book Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, where n is the number you are testing for primality.
这是S. Dasgupta、CH Papadimitriou 和 UV Vazirani所著的Algorithms一书中的伪代码，其中 n 是您要测试素性的数字。
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
Implementing Fermat's theorem should be faster then the sieve solution. However, there are Carmichael numbers that pass Fermat's test and are NOT prime. There are workarounds for this. I recommend consulting Section 1.3 in the fore mentioned book. It is all about primality testing and might be helpful for you.
实施费马定理应该比筛解法更快。但是，有些卡迈克尔数通过了费马测试并且不是素数。有解决方法。我建议参考上述书中的第 1.3 节。这完全是关于素性测试，可能对你有帮助。
回答by Milan
private static bool IsPrime(int number) {
if (number <= 3)
return true;
if ((number & 1) == 0)
return false;
int x = (int)Math.Sqrt(number) + 1;
for (int i = 3; i < x; i += 2) {
if ((number % i) == 0)
return false;
}
return true;
}
I can't get it any faster...
我不能再快了...
回答by Ant
As Mark said, the Miller-Rabin test is actually a very good way to go. An additional reference (with pseudo-code) is the Wikipedia articleabout it.
正如马克所说，米勒-拉宾测试实际上是一个非常好的方法。另一个参考（带有伪代码）是关于它的维基百科文章。
It should be noted that while it is probabilistic, by testing just a very small number of cases, you can determine whether a number is prime for numbers in the int (and nearly long) range. See this part of that Wikipedia article, or the Primality Proving referencefor more details.
应该注意的是，虽然它是概率性的，但通过仅测试极少数情况，您可以确定一个数字是否是 int（和接近 long）范围内的数字的质数。有关更多详细信息，请参阅该维基百科文章的这一部分，或Primality Proving 参考。
I would also recommend reading this articleon modular exponentiation, as otherwise you're going to be dealing with very very large numbers when trying to do the Miller-Rabin test...
我还建议您阅读有关模幂的这篇文章，否则在尝试进行 Miller-Rabin 测试时您将处理非常大的数字......
