题
我正在编写一个带有一些素数相关方法的小库。因为我已经完成了基础工作(也就是工作方法),现在我正在寻找一些优化。 当然,互联网是一个很好的地方。然而,我偶然发现了一个四舍五入的问题,我想知道如何解决这个问题。
在循环中,我用来测试一个数字,因为它的prityity搜索效率更高,直到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,结果大致相同。
解决方案
在下面的示例中,在最佳情况下(即,当数字小于或等于 maxPrime
时,查找数字是否为素数是O(1),对于64K,这是821,461缓冲区),并在某种程度上针对其他情况进行了优化(通过检查第一个820,000中仅64K的数据 - 大约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 + = 2”。而不是“idx ++”因为你只需要测试奇数(正如你在上面的评论中写的那样......)。
我不知道这是否是您正在寻找的,但如果您真的关心速度,那么您应该研究一下测试素质而不是使用筛子的可能方法。 Rabin-Miller 是Mathematica使用的概率素性测试。
我发布了一个使用筛子或Eratosthenes来计算质数的类:
正如马克所说,米勒 - 拉宾测试实际上是一个非常好的方法。另一个参考(使用伪代码)是维基百科文章它
应该注意的是,虽然它是概率性的,但通过测试极少数情况,您可以确定数字是否为int(和接近长)范围内的数字的素数。请参阅维基百科文章的这一部分或 Primality Proving参考以获取更多详细信息。
我还建议您阅读有关模幂运算的这篇文章,否则您将会去在尝试进行Miller-Rabin测试时要处理非常大的数字...
您可能需要查看费马的小定理。
这是来自书籍 S. Dasgupta,C.H。的算法的伪代码。 Papadimitriou和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
实施费马定理应该比筛选解决方案更快。然而,有一些卡迈克尔数字通过了费马的测试并且不是素数。有解决方法。我建议咨询前面提到的书中的第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;
我已经使用了这么多次..没有筛子那么快......但它确实有效。
这是我为解决其中一个欧拉而写的一个不错的功能:
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;
}
}
尝试筛选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
如果其他人感兴趣,这是我将上述穆罕默德程序转换为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
语句条件只是一个布尔表达式的原因:它使这样的事情成为可能。