更快速地检查数字是否为素数？

Question

我得到了这个代码,检查一个数字是否是一个素数:

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;
}

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

Answer 1

就在这里.例如,你可以分别检查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,则抛出异常会更合适,但我在这里跳过了' feature '.

在主循环之前检查所有偶数,而不仅仅是2(常见错误).

虽然这可能是家庭作业(7月!!!),整个互联网上有大量的链接会有类似的代码,所以我没有为他们做某人的功课.由于我的代码是在原始帖子之后几天添加的,因此OP从那时起就有时间进行研究和学习.