如何判断质数？

如何判断质数？

质数是指除1和本身以外不能被其它自然数整除的数。质数在密码学、数学、物理等领域有着广泛的应用。那么，如何判断一个数是不是质数呢？以下是几种常见的判断方法：

1、试除法：

试除法是最简单的一种判断质数的方法。即对于一个自然数n，从2到n-1枚举每个数，看是否能整除n。

bool isPrime(int n)
{
    if (n <= 1) return false; //质数定义，小于等于1的数不能是质数
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

2、试除法优化（适用于大一些的数）：

显然，我们只需要枚举到sqrt(n)就可以了，因为，如果有因子a * b=n，则一定有一个数小于等于sqrt(n)。

bool isPrime(int n)
{
    if (n <= 1) return false;
    int sqr = (int)sqrt(n);  //计算sqrt(n)
    for (int i = 2; i <= sqr; i++)
        if (n % i == 0) return false;
    return true;
}

3、线性筛法：

线性筛法是比较高效的一种判断质数的方法。

假设有一个自然数n，将从2到n枚举每个数，如果当前枚举的数字x是质数，那么将x的倍数标记为合数。

const int MAXN = 1000010;
int prime[MAXN], pNum = 0;  //prime[]存储所有素数，pNum是素数个数
bool p[MAXN] = { false };   //p[i] == true表示i是合数

void findPrime(int n)  //线性筛法求素数
{
    for (int i = 2; i <= n; i++)
    {
        if (p[i] == false)
        {
            prime[pNum++] = i;
            for (int j = i + i; j <= n; j += i)
                p[j] = true;
        }
    }
}

ps：线性筛法的优化可以查看符志凯老师的文献。

以上就是几种常见的判断质数的方法。对于小范围的数据可以直接使用试除法，而线性筛法适合不要求连续判断的多次询问。在实际应用中，根据具体情况选择使用方法才是最好的方式。