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.

Related Tags:

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!

Next Challenge: Cheryl's Birthday