检查数字是否为质数的算法[重复] 。

Question

这个问题在这里已经有了答案:

求质数的最快算法是哪种？ (14个答案)

封闭 24天前.

大家好！我来到这个关于如何检查数字是否是质数的算法，可能对我来说很好，但我想知道它是否可以改进。

我来到了这个算法，如何检查数字是否是质数，可能对我来说是好的，但我想知道它是否可以改进。

bool isPrime(int num)
{
    bool isPrime = 1;
    if (num <= 0)
    {
        return 0;
    }
    if (num == 1)
    {
        return 0;
    }
    for (int i = 2; i <= sqrt(num); ++i)
    {
        if (num % i == 0)
        {
            isPrime = 0;
        }
    }

    return isPrime;
}

先谢谢你

Answer 1

通过观察所有的质数都是6k±1的形式，除了2和3之外，这个算法可以进一步改进。这是因为对于某个整数k，且i=-1，0，1，2，3或4，所有的整数都可以表示为（6k+i）；2除以（6k+0），（6k+2），（6k+4）；3除以（6k+3）。所以更有效的方法是检验n是否被2或3整除，然后通过所有形式为6k±1的数来检验。

以上的实施。

#include <iostream>

bool isPrime(int n) {
    // Corner cases
    if(n <= 1) return false;
    if(n <= 3) return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if(n % 2 == 0 || n % 3 == 0) return false;

    for(int i = 5; i * i <= n; i = i + 6)
        if(n % i == 0 || n % (i + 2) == 0) return false;

    return true;
}

// Driver Program to test above function
int main() {
    std::cout << std::boolalpha
        << isPrime(11) << '\n'
        << isPrime(15) << '\n';
}

Answer 2

为了提高工作效率，不要计算... sqrt 如果偶数是被除数，你就不需要检查。另外，万一数字是负数，提前退出也很方便。这是我在C语言中的代码。

#define  boolean  int
#define   TRUE     1
#define   FALSE    0

boolean
isPrime(int number)
{
    if(number == 2)
        return TRUE;

    if(number < 2 || number % 2 == 0)
        return FALSE;

    /*
     * we only need to check until the sqrt
     * and we can omit the even numbers as well
     */
    for(int i = 3; i*i <= number; i += 2)
        if(number % i == 0)
            return FALSE;

    return TRUE;
}

Answer 3

一个不是质数的数字至少会被一个质数所除。因此，加快算法速度的方法(以内存为代价)是存储一个你已经遇到的质数列表，并且在每次迭代中只检查是否有这些质数除以你当前检查的数字。

Answer 4

1. 2是唯一的偶数质数。所以如果你从3开始循环，并增加 i 乘以2，那么你就可以切断一半的循环。

2. 而且只要找到第一个除数就可以断掉。

3. 赋值 sqrt(num) 到一个变量中，这样它就不会在每次迭代时都进行计算。

    if (num == 2)
    {
        return 1;
    }
    if (num % 2 == 0)
    {
        return 0;
    }
    int square_root = sqrt(num);
    for (int i = 3; i <= square_root; i += 2)
    {
        if (num % i == 0)
        {
            isPrime = 0;
            break;
        }
    }