C++ 判断质数的实现与优化

质数是指大于1的自然数，除了1和它本身外，不能被其他自然数整除的数。以下是几种C++判断质数的方法及其优化方案。

基础实现方法

1. 简单判断法（时间复杂度O(n)）

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

2. 优化判断法（时间复杂度O(√n)）

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