c++ - 检查数字是否为素数的算法

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

提前致谢

标签： c++algorithmprimes

Answer 1

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