为什么朴素素性测试算法不是多项式

Question

我想了解为什么以下朴素素性测试算法不是多项式。

IsPrime (n: an integer)
Begin
   For i=2 to n-1 do
     If (n % i == 0) then
        return (no)
     EndIf
   EndFor

   return (yes)
End

该算法被认为是输入n大小的指数。为什么这是真的？为什么下面的排序测试算法说是多项式而不是指数？

IsSorted (T[n]: an array of n integer)
Begin
  For i = 1 to n-1 do
     If (T[i] > T[i+1]) then
        return (no)
     EndIf
  EndFor

  return (yes)
End

Answer 1

输入大小通常以位为单位来测量。为了表示数字 n，输入大小将为 log2(n)。原始素性测试在 n 中是线性的，但在 log2(n) 中是指数的。