质数的判定(试除法)：

plan 1

完全从定义出发

时间复杂度：O(n)

bool is_prime(int n)
{
    if(n<2) return false;//如果不是严格大于1的话，就肯定不是质数
    for(int i=2;i<n;i++)//
        if(n%i==0)//如果能被除了1和本身以外的数整除，那就不是质数
            return false;
    return true;//满足以上条件的话，那么就是质数
}

plan 2

经过可行性剪枝后

时间复杂度：O(sqrt(n))

推导

若n可以被d整除，那么n也可以被n/d整除

所以n的因数都是成对出现的

所以我们可以只枚举这一对里的较小的一个

我们只遍历i≤n/i的情况

所以i[HTML_REMOVED]2[HTML_REMOVED]≤n

所以i≤√n

因此可以把算法降为O(sqrt(n))

bool is_prime(int n)
{
    if(n<2) return false;//如果不是严格大于1的话，就肯定不是质数
    for(int i=2;i<=n/i;i++)//i≤n÷i == i*i≤n
        if(n%i==0)//如果能被除了1和本身以外的数整除，那就不是质数
            return false;
    return true;//满足以上条件的话，那么就是质数
}