求质数

质数的定义

质数要符合两个条件

• 大于1的自然数
• 只有1和自己两个因数

试除法

试除法就是暴力解法，我们从2开始，将每一个数都与n来进行整除

代码

基本写法

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= n - 1; i ++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

优化

// 优化的原理
// 如果 n 可以被 b 整除，那么 n/b 也一定可以被 b 整除
// 那么此时我们只需要遍历较小的数即可
bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i ++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

时间复杂度

从代码来看，基本的写法的时间复杂度是$O(n)$，而优化后的写法时间复杂度是$O(\sqrt{n})$

注意事项

优化写法的循环判断条件不应写成以下两种写法

// 第一种
for(int i = 2; i <= sqrt(n); i ++)
// 这是因为sqrt函数速度慢

//第二种
for(int i = 2; i*i <= n; i ++)
// 这是因为 i*i 可能会溢出