数学-素数判定

bool isPrime(int n)
{
    if (n <= 1) return false;
    if (n == 2) return true;
    if (!(n & 1)) return false; // !(n & 1) <==> n % 2 == 0
    int limit = sqrt(n) + 1;
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return false;
    }

    return true;
}

时间复杂度为$O(\sqrt{n})$。因为： $$ n = d1 \times d2 $$ $d_1或d_2$中的一个取最大值是$\sqrt{n}$，如果有一个大于此数，就必有一个小于此数的因子，所以只需要检查到$\sqrt{n}$即可。