8

我得到了检查数字是否为素数的代码：

public static bool isPrime(int num)
{
    if (num == 1) return false;
    if (num == 2) return true;

    int newnum = Math.Floor(Math.Sqrt(num));

    for (int i = 2; i <= newnum; i++) 
        if (num % i == 0) return false;

    return true;
}

有没有更好更快的方法来检查一个数字是否是素数？

4

1 回答 1

22

就在这里。一方面，您可以单独检查 2，然后仅循环遍历奇数。这会将搜索循环减半。可能有更复杂的事情要做，但基本上应该回答你的问题。

更新代码：

    public static bool IsPrime(int number)
    {
        if (number < 2) return false;
        if (number % 2 == 0) return (number == 2);
        int root = (int)Math.Sqrt((double)number);
        for (int i = 3; i <= root; i += 2)
        {
            if (number % i == 0) return false;
        }
        return true;
    }

关于 SO 有很多重复的讨论，并且有很多关于各种素数搜索方法的链接。然而，由于这里的 OP 有一种方法来检查有符号的 32 位整数，而不是像无符号 64 位整数那样大得多的方法，因此快速检查显示 int.MaxValue 的截断平方根为 46340。因为我们仅循环遍历奇数，这将导致最大循环 23170 次迭代，在我看来，只要我们将讨论限制在 Int32 上，这相当快。如果问题是围绕 UInt64 进行的，那么可能应该研究其他更快的方法。

上面的代码处理任何int 值，而不仅仅是 1 的特殊情况。也许你有一个限制输入的 NumericUpDown 控件，但我不知道仅从显示的函数。有人可能会争辩说，如果输入数字 < 2，则抛出异常会更合适，但我在这里跳过了那个“特性”。

在主循环之前检查所有偶数，而不仅仅是 2（常见错误）。

虽然这可能是家庭作业（在 7 月！！！），但整个 Internet 上有大量链接具有类似的代码，因此我不会为他们做任何人的作业。由于我的代码是在原始帖子后几天添加的，因此 OP 从那时起就有时间研究和学习。

于 2013-07-10T19:17:56.130 回答