c# - 我如何测试素数？

Question

我正在用一些与素数相关的方法编写一个小库。由于我已经完成了基础工作(又名工作方法)，现在我正在寻找一些优化。 当然，互联网是这样做的绝佳场所。然而，我偶然发现了一个舍入问题，我想知道如何解决这个问题。

在我用来测试一个数字的素数的循环中，搜索到 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，结果大致相同。

Answer 1

我想这是你的问题:

for (int idx = 3; idx < flooredAndSquared; idx++)

应该是

for (int idx = 3; idx <= flooredAndSquared; idx++)

所以你不会得到平方数作为质数。此外，您可以使用“idx += 2”而不是“idx++”，因为您只需要测试奇数(正如您在上面的评论中直接写的...)。