ECE 150 Fundamentals of programming

Determine if a number $n$ is prime by:

• checking if it is divisible by two,
• and if not, checking if it is divisible by all odd integers starting with 3 up to the integer square root of $n$.

Next, optimize your algorithm by avoiding multiples of three. Observe that if $k$ is divisible by $3$, then neither $k + 2$ nor $k + 4$ is divisible by $3$.