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

Question

This question already has answers here:

Which is the fastest algorithm to find prime numbers?

(14个回答)


在6个月前关闭。




大家好!

我来到了这个算法，研究如何检查数字是否为素数，也许对我来说很好，但是我想知道它是否可以改进

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

提前谢谢

最佳答案

通过观察所有素数都为6k±1的形式(2和3除外)可以进一步改进该算法。这是因为对于某些整数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';
}

关于c++ - 检查数字是否为素数的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62150130/

上一篇：c++ - 为什么地址一样？

下一篇：c++ - 对于带移位的循环

Answer 1

通过观察所有素数都为6k±1的形式(2和3除外)可以进一步改进该算法。这是因为对于某些整数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';
}