# 3 ways to check if a value is prime

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.

## Brute Force

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


## Toss out the evens

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


## Every factor between 0 and sqrt(input) has corresponding factor between sqrt(input) and input

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!