我正在编写一个带有一些素数相关方法的小库。因为我已经完成了基础工作（也就是工作方法），现在我正在寻找一些优化。当然，互联网是一个很好的地方。然而，我偶然发现了一个四舍五入的问题，我想知道如何解决这个问题。
在循环中，我用它来测试一个数字，因为它的搜索效率更高，搜索直到sqrt（n）而不是n / 2甚至n - 1.但由于舍入问题，一些数字会被跳过，因此会跳过一些素数！例如，第10000个素数应为：104729，但“优化”版本最终为：103811。
一些代码（我知道，它可以进行更多优化，但我一次只能处理一件事）：
/// <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;
}
我知道平方部分让我失望（或者我失败了），也尝试过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;
}
}
尝试sieve of 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;
}
我不能更快地得到它......
我认为Prime numbers and primality testing是有用的，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
如果其他人感兴趣，这是我将穆罕默德的程序转换为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语句条件只是一个布尔表达式：它使这样的事情成为可能。
我猜这是你的问题：
for (int idx = 3; idx < flooredAndSquared; idx++)
这应该是
for (int idx = 3; idx <= flooredAndSquared; idx++)
所以你不能得到方数作为素数。此外，您可以使用“idx + = 2”而不是“idx ++”，因为您只需测试奇数（正如您在上面的注释中所写的那样......）。
我不知道这是否是您正在寻找的，但如果您真的关心速度，那么您应该研究一下测试素质而不是使用筛子的可能方法。 Rabin-Miller是Mathematica使用的概率素性测试。
我发布了一个使用Eratosthenes筛子来计算质数的类：
Is the size of an array constrained by the upper limit of int (2147483647)?
正如马克所说，米勒 - 拉宾测试实际上是一个非常好的方法。关于它的另一个参考（使用伪代码）是Wikipedia article。
应该注意的是，虽然它是概率性的，但通过测试极少数情况，您可以确定数字是否是int（和接近长）范围内的数字的素数。有关详细信息，请参阅this part of that Wikipedia article或the Primality Proving reference。
我还建议在模幂运算中读取this article，否则在尝试进行Miller-Rabin测试时你会处理非常大的数字......
你可能想看看Fermat's little theorem。
以下是Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani一书中的伪代码，其中n是您为素性测试的数字。
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
实施费马定理应该比筛选解决方案更快。然而，有一些卡迈克尔数字通过了费马的测试并且不是素数。有解决方法。我建议咨询Section 1.3 in the fore mentioned book。这完全是关于素性测试，可能对你有所帮助。
试试这个...
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;
我已经使用了这么多次..没有筛子那么快......但是它有效。
这是我为解决其中一个欧拉写的中途体面的功能：
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;
}
}
我有一个快速算法来检查素数。如果您知道素数的形式为6k±1，则可以改进算法，但2和3除外。因此，首先您可以测试输入是否可以被2或3整除。然后，检查表格的所有数字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;
}
}