ECE 150 Fundamentals of programming

In all the projects, you are asked to create an array of capacity n and to then apply the algorithm as described; however, right from the start, we know all even numbers other than $2$ are not prime, so why not ignore these both in our storage and our implementation of the algorithm.

Now, to understand this optimization, we must first remember a few facts from secondary school:

1. If $p$ and $q$ are either both odd or both even, then $p + q$ must be even.
2. If one of $p$ and $q$ is even and the other is odd, then $p + q$ must be odd.
3. If $p$ is even, $p^2$ is also even; and if $p$ is odd, $p^2$ is odd.

Therefore, we need only allocate an array of capacity n/2 and to then assume that array[n] flags whether or not 2*n + 1 is prime. Similarly, when we determine that $p$ is prime, we need only flag that $p^2$, $p^2 + 2p$, $p^2 + 4p$, etc. are not prime, because $p^2$ is odd for all odd numbers, so $p^2 + p$, $p^2 + 3p$, etc. must all already be even, while $p^2 + 2p$, $p^2 + 4p$, etc. must all be odd.