Why naive primality test algorithm is not polynomial

Question

I would like to understand why the following naive primality test algorithm is not polynomial.

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

   return (yes)
End

This algorithm is said to be exponential in the size of the input n. Why is it true? And why the following sorting test algorithm is said polynomial and not exponential?

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

The input size is typically measured in bits. To represent the number n the input size would be log2(n). The primitive primality test is linear in n, but exponential in log2(n).

Answer 2

The naive primarily test is polynomial in the value of the input (that is, the actual number which the function receives), but exponential in the size (bits, bytes, etc.) of the input.

If you have a number n consisting of b bits, we have b = O(log n) and also n = O(2b).

The running time is thus O(n) or O(2b).