algorithm - 查找素数的简单算法的复杂性

我想知道这个简单算法找到质数的渐近复杂度是O（n）：

PrimeNumber(n)
Int i;
If (n%2=0) then { return "not prime"; }
Else {
  For(i=3;i<(√n)+1;i=i+2;){
    If (n%i=0) then {return "not prime";}
  }
}
return "prime";

最佳答案

时间复杂度O(sqrt(n))，因为循环迭代自身(sqrt(n)+1-3)/2倍，在O(sqrt(n))。
注意，由于O(sqrt(n))是O(n)的一个子集，所以说它是O(n)也是正确的，但是这个界限并不紧。