**Question:** A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. Given an input value check if it's a prime.

Related Tags:

Let's think about the simplest way to solve this. We could just divide our input by every number less than itself. If we can get to 1 without crossing a divisor that gives us a remainder of 0, then our value is prime.

```
public static boolean isPrimeNaive(int input) {
if (input <= 1)
return false;
for (int i = input - 1; i >= 2; i--) {
if (input % i == 0)
return false;
}
return true;
}
```

Note that all primes must be odd. The only exception is the number 2. So we can simplify our problem above by placing a line of code to check that our input value is odd.

```
public static boolean isPrimeSkipTwos(int input) {
if (input <= 1)
return false;
// Only even prime number is 2
if (input == 2)
return true;
// return false if input is even
if (input % 2 == 0)
return false;
for (int i = input - 2; i > 2; i -= 2) {
if (input % i == 0) return false;
}
return true;
}
```

If our number was composite, then it would have multiple pairs of factors. For example, for the number 40, we have 2 x 20, 4 x 10, and 5 x 8. The squareroot of 40 is 6.32. So any factors that exist above this number (20, 10, 8) have a corresponding factor below it (2, 4, 5). We can use this property to simplify our algorithm even more.

```
public static boolean isPrimeSqRoot(int input) {
if (input == 2)
return true;
if (input <= 1)
return false;
if (input % 2 == 0)
return false;
/**
* Only up to the square root.
* If there exists a factor between input and sqrt(input)
* then that value will have a corresponding factor between 3 and sqrt(input)
*/
for (int i = input - 2; i >= Math.sqrt(input); i -= 2) {
if (input % i == 0)
return false;
}
return true;
}
```

Came up with a better solution or have a question? Comment below!

Next Challenge: Project Euler Problem 46: Goldbach's other conjecture