Algorithm to generate all the primes up to given bound $n.$ It uses an array $.$

$n,$ and runs as follows:

for $k=2$ to $n$ do

for $k=2$ to $\sqrt[\phantom{2}]{n}$ do

if $A[k]=1$ then

$i=2k$

while $in$ do

$A[i]=0,i=i+k$

Exercise $1$

One drawback of the above algorithm is its use of space: it requires an array of size $n.$

Show how to modify the algorithm, without substantially increasing its running time,

so that one can enumerate all the primes up to $n,$ using an auxiliary array of size just

$O(\sqrt[\phantom{2}]{n})$