$\Huge\color{orchid}{点击此处获取更多干货}$

质数的定义及判断方法

质数的定义在小学的时候就学过，指的是一个正整数的约数只有1和自身，不满足这样性质的正整数就叫做合数。由此可以先判断1不是质数，而2是质数$(2=1*2)$，对于不小于3的正整数$x$，它是质数就代表着$2 \sim x-1$的整数都不能整除$x$，因此可以很简单的遍历$2 \sim x-1$，判断其中是否有整除$x$的数。

与此同时，还可以注意到，不小于3的合数$x$，其不同约数个数可以是奇数也可以是偶数，并且当且仅当它是完全平方数时，其约数个数才是奇数。如果将每个约数两两配对的话，剩下那个无法被配对的约数一定是$\sqrt{x}$。两两配对的约数中，必定有一半在$\sqrt{x}$以下，另一半则在$\sqrt{x}$以上。因此枚举范围可以少一半，从$2\sim x-1$缩减为$2\sim \left \lfloor \sqrt{x} \right \rfloor$

C++ 代码

/**
* @brief 质数判断
* @param x 待判断的数
* @retval true 是质数
* @retval false 不是质数
*/
bool isPrime(int x) {
    if (x == 1) {       //1不是质数
        return false;
    }
    if (x == 2) {       //2是质数
        return true;
    }
    //不小于3的要试除
    for (int i = 2; i <= x / i; i++) {  //i*i<=x容易溢出
        if (x % i == 0) {  
            return false;
        }
    }
    return false;
}