Consider the following algorithm to determine if a given positive interger n is prime.

For each integer i between $2$ and $$

$$

n$,$ check if i is a factor of n$,$ i$.$e$.,$ if dividing n by i leaves a remainder

of $0.$ If the answer is $$yes$$ for any i$,$ return that n is composite. Otherwise, return that n is prime.

What is the size of the input to this problem? Is it $1$ because there is only one number in the input?

Is it n because the input is n$?$ It is not the first option, because the input may be an immensely large

number which we cannot represent with a constant size. It is not the second option, since the value

of the input is n$,$ which is not the same as the size of the input. The correct way to think about the

input size in this case is the number of bits needed to represent n$.$