我正在编写一个带有一些素数相关方法的小库。由于我已经完成了基础工作(又名工作方法),现在我正在寻找一些优化。当然,互联网是这样做的好地方。然而,我偶然发现了一个舍入问题,我想知道如何解决这个问题。
在循环中,我用来测试一个数字的素数,搜索直到 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;
}
I know the squared part fails me (or I fail), tried Math.Ceiling as well, with about the same results.