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

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

提前致谢

Answer 1

2 是唯一的偶素数。所以如果你开始循环表格 3 并将 i 增加 2，那么你可以将循环减半。
并且只要找到第一个除数就可以破解。
将 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;
        }
    }

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

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

Answer 4

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

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

Algorithm of checking if the number is prime

c++

algorithm

primes