我怎样才能测试素性？
我正在写一个带有一些素数相关方法的小库。 因为我已经完成了基础工作（也称为工作方法），现在我正在寻找一些优化。 当然，互联网是一个很好的地方。 然而，我偶然发现了一个四舍五入的问题，我想知道如何解决这个问题。
在循环中，我用它来测试一个数字，因为它的搜索效率更高，搜索直到sqrt（n）而不是n / 2甚至n – 1.但是由于舍入问题，一些数字会被跳过，因此会跳过一些素数！ 例如，第10000个素数应为：104729，但“优化”版本最终为：103811。
一些代码（我知道，它可以进行更多优化，但我一次只能处理一件事）：
/// /// Method for testing the primality of a number eg: 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 /// /// Number to be tested on primality /// True if the number is prime, false otherwise 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; } 我知道平方部分让我失望（或者我失败了），也尝试过Math.Ceiling，结果大致相同。
可悲的是，我之前没有尝试过算法。 但是如果你想有效地实现你的方法，我建议做一些缓存。 创建一个数组来存储小于定义阈值的所有素数，填充此数组，然后在其中搜索/使用它。
在下面的示例中，查找数字是否为素数在最佳情况下为O（1）（即，当数字小于或等于maxPrime ，对于64K缓冲区为821,461），并且在某种程度上针对其他情况进行了优化（通过检查第一个820,000中的64K数字的mod – 大约8％）。
（注意：不要把这个答案作为“最佳”方法。它更像是如何优化实现的一个例子。）
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; } }
我猜这是你的问题：
for (int idx = 3; idx < flooredAndSquared; idx++)
这应该是
for (int idx = 3; idx <= flooredAndSquared; idx++)
所以你不能得到方数作为素数。 此外，您可以使用“idx + = 2”而不是“idx ++”，因为您只需要测试奇数（正如您在上面的注释中所写的那样......）。
我不知道这是否是您正在寻找的，但如果您真的关心速度，那么您应该研究用于测试素数的可能性方法而不是使用筛子。 Rabin-Miller是Mathematica使用的概率素性测试。
我发布了一个使用筛子或Eratosthenes来计算素数的类：
数组的大小是否受int的上限（2147483647）约束？
正如马克所说，米勒 – 拉宾测试实际上是一个非常好的方法。 另一个参考（使用伪代码）是关于它的维基百科文章 。
应该注意的是，尽管它是概率性的，但通过仅测试极少数情况，您可以确定数字是否为int（和接近长）范围内的数字的素数。 有关更多详细信息，请参阅该Wikipedia文章的这一部分或Primality Proving参考 。
我还建议阅读这篇关于模幂运算的文章 ，否则你在尝试进行Miller-Rabin测试时会处理非常大的数字……
你可能想看看费马的小定理 。
这是来自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
实施费马定理应该比筛选解决方案更快。 然而，有一些卡迈克尔数字通过了费马的测试并且不是素数。 有解决方法。 我建议在前面提到的书中咨询第1.3节 。 这完全是关于素性测试，可能对你有所帮助。
试试这个…
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;
我已经使用了这么多次..没有筛子那么快......但是它有效。
这是我为解决其中一个欧拉写的中途体面的function：
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; } }
我有一个快速算法来检查素数。 如果你知道质数的forms是6k±1，你可以改进你的算法，除了2和3.所以，首先你可以测试输入是否可以被2或3整除。然后，检查所有forms的数字6k ±1≤√输入。
bool IsPrime(int input) { //2 and 3 are primes if (input == 2 || input == 3) return true; else if (input % 2 == 0 || input % 3 == 0) return false; //Is divisible by 2 or 3? else { for (int i = 5; i * i <= input; i += 6) { if (input % i == 0 || input % (i + 2) == 0) return false; } return true; } }
尝试使用eratosthenes的筛子 – 这应该可以解决根和浮点问题。
至于floor ，乘坐ceiling会更好。
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; }
我不能更快地得到它......
我认为素数和素数测试是有用的，并且AKS算法听起来很有趣，即使它与基于概率的测试相比不是特别实用。
这对于测试质数非常快（vb.net）
Dim rnd As New Random() Const one = 1UL Function IsPrime(ByVal n As ULong) As Boolean If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then return false End If Dim s = n - one While s Mod 2 = 0 s >>= one End While For i = 0 To 10 - 1 Dim a = CULng(rnd.NextDouble * n + 1) Dim temp = s Dim m = Numerics.BigInteger.ModPow(a, s, n) While temp <> n - one AndAlso m <> one AndAlso m <> n - one m = (m * m) Mod n temp = temp * 2UL End While If m <> n - one AndAlso temp Mod 2 = 0 Then Return False End If Next i Return True End Function
如果其他人感兴趣，这是我将上述Mohammad程序转换为VBA。 我添加了一个检查以排除1,0和负数，因为它们都被定义为非素数。
我只在Excel VBA中测试了这个：
Function IsPrime(input_num As Long) As Boolean Dim i As Long If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime. IsPrime = False: Exit Function ElseIf input_num = 2 Then IsPrime = True: Exit Function '2 is a prime ElseIf input_num = 3 Then IsPrime = True: Exit Function '3 is a prime. ElseIf input_num Mod 2 = 0 Then IsPrime = False: Exit Function 'divisible by 2, so not a prime. ElseIf input_num Mod 3 = 0 Then IsPrime = False: Exit Function 'divisible by 3, so not a prime. Else 'from here on, we only need to check for factors where '6k ± 1 = square root of input_num: i = 5 Do While i * i <= input_num If input_num Mod i = 0 Then IsPrime = False: Exit Function ElseIf input_num Mod (i + 2) = 0 Then IsPrime = False: Exit Function End If i = i + 6 Loop IsPrime = True End If End Function
你的for循环应该如下所示：
for (int idx = 3; idx * idx <= test; idx++) { ... }
这样，您可以避免浮点计算。 应该运行得更快，它会更准确。 这就是为什么for语句条件只是一个布尔表达式：它使这样的事情成为可能。