编写函数判断一个数n是否为质数

判断一个数是否为质数，一般有两种方法：试除法和埃氏筛法。

试除法的思路是：从2开始，依次将n除以2、3、4……sqrt(n)，如果能整除，则n不是质数；否则n是质数。sqrt(n)表示n的算术平方根。

代码如下：

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

埃氏筛法的思路是：从2开始，将所有能被2整除的数标记为合数；然后再找到下一个未被标记的数，即3，将所有能被3整除的数标记为合数；以此类推，直到sqrt(n)。

代码如下：

bool isPrime(int n) {
    if (n < 2) {
        return false;
    }
    vector<bool> isComposite(n+1, false);
    for (int i = 2; i <= sqrt(n); i++) {
        if (!isComposite[i]) {
            for (int j = i*i; j <= n; j += i) {
                isComposite[j] = true;
            }
        }
    }
    return !isComposite[n];
}

其中，vector<bool> isComposite(n+1, false) 表示创建一个n+1大小的布尔型数组，初始值都为false。