检查数字是否为质数的更快方法? [英] Faster way to check if a number is a prime?

问题描述

我得到了这段代码，用于检查数字是否为素数:

I got this code that checks if a number is a prime:

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

有没有更好，更快的方法来检查数字是否为质数?

Is there any better and faster way to check if a number is a prime?

推荐答案

是的.对于一个，您可以单独检查2，然后仅循环访问奇数.这样可以将搜索循环减少一半.可能还有更多复杂的事情要做，但基本上可以回答您的问题.

Yes there is. For one, you could check for 2 separately and then loop through only odd numbers. That would cut the search loop in half. There could be more elaborate things to do but basically that should answer your question.

已更新代码:

    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展开的，那么可能应该研究其他方法以加快速度.

There are many duplicate discussions on SO and plenty of links about various primality search methods. However, since the OP here has a method to check a signed 32-bit integer, and not something much larger like an unsigned 64-bit integer, then a quick check shows the truncated square root of int.MaxValue to be 46340. Since we are looping through only odd numbers that would result in a maximum loop of 23170 iterations, which in my opinion is quite fast as long as we are limiting the discussion to Int32. If the question revolved around UInt64, then other methods should maybe be investigated regarding faster.

上面的代码处理的是 any int值，而不仅仅是1的特殊情况.也许您有一个NumericUpDown控件来限制输入，但是我不仅仅从显示的函数中知道这一点..有人可能会争辩说，如果输入数字小于< 1，则抛出异常会更合适.2，但是我在这里跳过了"功能".

The code above takes care of any int value, not just the special case of 1. Perhaps you have a NumericUpDown control that limits the inputs but I don't know that from just the function shown. One could argue that it would be more proper to throw an exception if the input number is < 2, but I skipped that 'feature' here.

所有偶数，而不仅仅是2(常见错误).

All even numbers are checked before the main loop, not just 2 (a common mistake).

尽管这可能是家庭作业(七月份！！！)，但是Internet上有很多链接都有类似的代码，所以我不为他们做某人的作业.由于我的代码是在原始帖子发布几天后添加的，因此OP从那时起就有时间进行研究和学习.

And while this could be homework (in July!!!), there are tons of links throughout the Internet that would have similar code so I am not doing someone's homework for them. Since my code was added days after the original post, the OP has had time to research and learn since then.

这篇关于检查数字是否为质数的更快方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！