Here is a naive algorithm for isPrime$($x$)$ that runs in O$($n$)$ time, where n is the value of the input

$($and k $=$ log n is the size of the input$).$

def isPrime$($n$)$:

$//$ INPUT: n is an integer $>1$

$//$ OUTPUT: True if n is prime, False otherwise

for i in range $(2,$n$-1)$:

if $($n$\%$i $==0)$:

return False

return True

a$)$ Suppose we change the algorithm by replacing n$-1$ in line $2$ by n$+1.$ Prove that this algorithm

is incorrect, by showing that there are inputs for which it returns the wrong answer.

NOTE: this is known a proof by counterexample.

b$)$ Suppose we change the algorithm by replacing n$-1$ on line $2$ by int$($sqrt$($n$))+1.$ Prove that this

algorithm is correct, by showing that for all inputs, it returns the correct answer.

c$)$ Give an analysis of the running time for algorithm $($b$)$ as a function of input value n

d$)$ Using your solution from $($c$),$ find running time for algorithm $($b$)$ as a function of input size k$.$

NOTE: if the input value is n$,$ then the input size k is log n$.$ Given that log n $=$ k$,$ taking exponent

of both sides, we get n $=2$

k

$.$ So you can plug $2$

k

into your function of n to get the function of k