A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. The value 17 is prime because nothing between 2 and 16 divides it evenly. The value 18 is not prime because it splits into 2 * 9, so it has divisors other than 1 and 18.

The definition rules out everything at or below 1. The number 1 is not prime, because a prime must be strictly greater than 1 and 1 has only a single positive divisor rather than two distinct ones. The number 0 is not prime, and every negative number is not prime either, since the definition only applies to integers greater than 1. These cases are handled with a single guard before any divisor testing begins.

The number 2 is the smallest prime and the only even prime, since every other even number is divisible by 2 and therefore composite. Code that skips even candidates to save work has to let 2 through first, or it will wrongly report 2 as not prime.

Key Constraints:

Intuition

If n is composite, some integer between 2 and n - 1 divides it evenly. Try each candidate divisor in that range. If any one divides n with no remainder, n is not prime. If none do, n is prime.

The guard for values at or below 1 comes first. After that guard, even 2 works correctly: the range from 2 to n - 1 is empty for n = 2, so no divisor is found and the result is prime.

Algorithm

Example Walkthrough

Input:

The value 17 is greater than 1, so the loop runs. The candidate 2 does not divide 17 evenly, and neither does 3, 4, and so on up through 16. Every remainder is non-zero, so no divisor is ever found. The loop finishes without returning early, so the answer is true. The value 17 is prime.

Code

Intuition

Divisors come in pairs. If a * b = n, then one of a and b is at most the square root of n and the other is at least that square root. So any divisor larger than the square root has a matching smaller one, and finding the smaller partner is enough.

The search only has to run candidates up to and including the square root of n. If none divides n there, none exists at all, and n is prime. For 18, the square root is about 4.24, so testing 2, 3, and 4 is enough: 2 divides 18, so it is composite right away. To avoid floating-point square roots, the loop condition i * i <= n tests the same boundary using only integer multiplication.

Algorithm

Example Walkthrough

Input:

The value 18 is greater than 1, so the loop runs. The first candidate is 2, and 2 * 2 = 4 is less than or equal to 18, so the test proceeds. The remainder of 18 divided by 2 is 0, so a divisor is found and the result is false without checking any further. The square root of 18 is about 4.24, so the loop would only have run i from 2 to 4 even if no early divisor existed. The value 18 is not prime.

Code

Intuition

The square-root loop still tests many candidates that cannot possibly be divisors. After 2 and 3 are handled, no prime is divisible by 2 or by 3, so any real divisor must avoid both. Look at the integers around a multiple of 6: the values 6k, 6k + 2, and 6k + 4 are all even, and 6k + 3 is divisible by 3. That leaves only 6k - 1 and 6k + 1 as candidates that are not already ruled out. Every prime greater than 3 falls into one of those two forms.

So after checking divisibility by 2 and 3 directly, the loop can start at 5 and step by 6, testing i and i + 2 each time. That pair is exactly 6k - 1 and 6k + 1. This visits roughly a third of the candidates the plain square-root loop would, while still covering every possible prime divisor up to the square root.

Algorithm

Example Walkthrough

Input:

The value 97 is greater than 1 and is neither 2 nor 3. It is not divisible by 2 and not divisible by 3, so the loop begins with i = 5. Since 5 * 5 = 25 is at most 97, the test runs: 97 is not divisible by 5 and not by 7, so i advances to 11. Since 11 * 11 = 121 is greater than 97, the loop stops. No divisor was found, so the answer is true. The value 97 is prime, and only the candidates 5 and 7 had to be tested.

Code