【算法】判断一个数是否是质数的四种常用方法

【算法】判断一个数是否是质数的四种常用方法

算法1:暴力枚举

时间复杂度为O(n²)

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i < n;i ++){ //这个很好理解，从最小的质数2开始枚举到n - 1
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}
1
2
3
4
5
6
7
8
9

算法2:使用根号sqrt优化

由于sqrt(n) x sqrt(n)<=n，所以n中只能包含一个sqrt(n)的质因子

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i <= sqrt(n);i ++){ //优化部分
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}
1
2
3
4
5
6
7
8
9

不推荐使用，原因：sqrt函数运行很慢，每次执行都需要运行

也可以稍微优化一下，定义一个变量存储sqrt(n)的值

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    int x = sqrt(n);
    for(int i = 2;i <= x;i ++){ //优化部分
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}
1
2
3
4
5
6
7
8
9
10

算法三：使用i*i<=n优化

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i * i <= n;i ++){ //和用根号差不多
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9

不推荐使用，原因：i*i可能会溢出int范围

算法四：使用i<=n/i优化

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;
}
1
2
3
4
5
6
7
8
9

同时避免算法二、算法三的问题