请求解释这段质数判断方法的时间复杂度

先看你给出的代码：

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

时间复杂度分析 #

时间复杂度用大O符号描述算法的最坏执行情况，我们直接聚焦核心的循环逻辑：

• 循环的终止条件是i < sqrt(n)+1，也就是说循环最多会执行到i接近√n的位置。忽略+1这类常数项（时间复杂度不关心固定的常数偏移），循环的执行次数和√n成正比。
• 最坏情况是当n本身是质数时，循环会完整走完所有次数，没有提前返回false，此时算法的执行时间由√n次循环决定。

所以这个质数判断方法的时间复杂度是O(√n)。

额外补充：这个算法比遍历到n-1的版本高效，原因是如果n存在大于√n的因数，那它必然对应一个小于√n的因数，因此只需检查到√n就能确定n是否为质数。

内容的提问来源于stack exchange，提问作者user20541776