複雜性找到一個素數

Question

我想知道，如果這個簡單的算法漸近複雜性找到一個素數爲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"; 

Answer 1

時間複雜度爲O(sqrt(n))，由於環路重複自己(sqrt(n)+1-3)/2次，這是在O(sqrt(n))。

注意，因爲O(sqrt(n))是子集的O(n)，這也是正確的說是O(n) - 但結合不緊。