检查一个数字是否为质数的算法

Question

大家好！

我找到了一个检查数字是否为质数的算法，它似乎对我来说很不错，但我想知道它是否可以改进。

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

提前致谢

- NixoN

---

使用 false 和 true 而不是 0 和 1 可以显然地改进它。 - john

如果你发现一个数字不是质数，可以通过跳出循环来改进它。 - john

我认为它们是整数;)。它们可以转换为“bool”，但为什么要这样做呢？你也可以用“42”来代替“true”，但当你想表达“true”的时候，使用“true”会使你的代码更易读。 - 463035818_is_not_a_number

https://github.com/jselbie/isprime/blob/master/isprime.cpp - selbie

如果你的代码能够正常运行，请将其发布在Code Review上，以帮助改进它。 - lnxkrnl

Answer 1

算法可以进一步改进，观察到所有的质数都是6k±1的形式，除了2和3。这是因为所有整数都可以表示为(6k+i)，其中i=-1,0,1,2,3或4，对于某个整数k；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';
}

- Parth Sharma

Answer 2

非质数一定可以被至少一个质数整除。因此，为了加速算法（代价是占用内存），可以存储已经遇到的质数列表，并且在每次迭代中仅检查这些质数是否能整除当前正在检查的数字。

- user3177387

Answer 3

为了使这更有效率，不要计算数字的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;
}

- lnxkrnl

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

- Rafik Farhad

---

这个想法不错，但实现得很差。 - john

如果编译器没有提升 sqrt(num) 并在每次迭代中计算它会怎么样？编辑：我看到这不是你介绍的，但还是有点可怕！;-) - underscore_d

不能保证编译器会在每次循环迭代中优化掉 sqrt(num)。考虑将其分配给一个变量常量，并让 for 循环条件语句评估 i < that value。 - selbie

哦，抱歉，我忘记处理偶数情况了，已经编辑答案了。 - Rafik Farhad