Math $3343*$ Homework $4$

Consider the pseudocode for computing an array of prime numbers less than or equal to $n.$

INPUT $n-$ positive integer

OUTPUT $p$ is an array of prime numbers less than or equal to is the number of

prime numbers less than or equal to $n.)$

$k=0$

for $c=2,$dotsn

for $d=2,3,$dotsc$-1$

if remainder $(\frac{c}{d})=0$

then $c$ is composite, stop loop and go to next $c$ value

end if statement

end for loop

If inner loop cycled all the way through

then $k=k+1$

then $p_k=c$

end if statement

end for loop

The algorithm can be summarized in this way. Consider whether each integer from $2$ to $n$ is

prime by dividing it by all integers greater than $1$ and less than the number being considered.

If one of those lesser numbers divides evenly into our candidate prime, then it's composite.

Otherwise it is prime and we add that candidate number to the list.

This algorithm is implemented in the code prime$\_$list$\_$slow.m$.$ As the code name sug$-$

gests, we can accelerate the speed of the code. That is the subject of this homework.

Theorem $1$ If $c$ is not divisible by any prime number less than $c,$ then $c$ is a prime number.

Theorem $2$ If $c$ is not divisible by any integer between two and $\sqrt[\phantom{2}]{c},$ then $c$ is prime.

$(20$ points$)$ Explain how the the two theorems above can be used to accelerate the code

prime$\_$list$\_$slow.m created in class $($and available via Blackboard$).$

$(20$ points$)$ Write a pseudocode incorporating these changes with input $n$ and output

$pin{N}^{(n)},$ which is an array of all prime numbers less than or equal to $n.$

$(20$ points$)$ Create a Matlab function, titled prime$\_$list that implements your pseu$-$

docode above. Your function should have the following input and output:

Input $n-$ positive integer