Create a method that checks whether an input integer is prime or not. For this question we will take a look at a simple algorithm for determining primes and optimize it.
What are some common characteristics of numbers that are not prime.
The simplest algorithm would sequentially check all the numbers (n) up to the input number and return false if at any point input % n = 0.
Two major ways we can improve this algorithm is by immediately returning false if the number is divisible by 2 (a very likely occurrence) and also by only iterating only till the square root of the input (after which checking is un-needed).

isPrime(int input)
    if (input % 2 == 0 && input != 2)
       return false;

    for (n = 3; n <= Math.sqrt(input); n += 2)
       if (input % n == 0)
          return false;

    return true;