Question $2$

Consider the following algorithm

MYSTERY$($n$)$

$1$ new array s$[1...$n$]$

$2$ s$[1]=0$

$3$ for i $=2$ to n

$4$ s$[$i$]=1$

$5$ for p $=2$ to p$=$floor$($sqrt$($n$))$

$6$ if s$[$p$]==1$

$7$ for f $=$ p to f $=$ floor$($n$/$p$)$

$8$ s$[$f $*$ p$]=0$

$9$ for i $=1$ to n

$10$ if s$[$i$]==1$

$11$ print i

$2\mathrm{.}1$ Question $2.($a$)$

What is the purpose of lines $1-4?$

$2\mathrm{.}2$ Question $2.($b$)$

What is the purpose of lines $9-10?$

$2\mathrm{.}3$ Question $2.($c$)$

What is printed upon execution of MYSTERY $(12)?$

$2\mathrm{.}4$ Question $2.($d$)$

Rewrite MYSTERY as a recursive program.

$2\mathrm{.}5$ Question $2.($e$)$

What, in big$-$O notation, is the time complexity of MYSTERY$($n$)?$

Hint $1+1/2+1/3+...+1/$n$=$ O$($log$($n$))$

$2\mathrm{.}6$ Question $2.($f$)$

What is the purpose of the program as a whole?