Skip to the content of the web site.

Project H.4: Iterative primality testing

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$.