question

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

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

`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;