Prime Check and Neighbouring Primes

Tests whether an integer is prime by trial division. When the smallest prime factor equals n itself, n is prime; any smaller factor is proof that it is not. The nearest primes below and above are shown as well.

A prime number is an integer of 2 or greater that cannot be divided evenly by anything except 1 and itself. The sequence begins 2, 3, 5, 7, 11 and never ends. The straightforward way to test a number is to divide it by each smaller number in turn and see whether anything goes in evenly. This is called trial division.

This calculator reports the smallest divisor it finds. When that value equals n itself, nothing smaller divided it, so n is prime. When a smaller value appears, it is proof that n has a factor, so n is not prime.

How far do you have to divide

You do not need to try every number from 2 up to n − 1. Suppose n has a factor other than 1, and write n = a × b with a the smaller of the two. Then a × a is at most a × b, which is n.

n = a \times b, \quad a \leq b \implies a \leq \sqrt{n}

So if n has a factor at all, the smaller one always sits at or below the square root of n. Put the other way round, once you have tried everything up to $\sqrt{n}$ without success, there is nothing further to find. For n = 10000 you only test up to 100, and for n = 1000000 only up to 1000.

Example

Take the default input n = 91. Since $\sqrt{91}$ is about 9.5, testing up to 9 is enough.

Divide by 2. 91 is odd, so no
Divide by 3. Its digits add to 9 + 1 = 10, which is not a multiple of 3, so no
Divide by 5. It does not end in 0 or 5, so no
Divide by 7. 91 ÷ 7 = 13, so yes

The search stops here. The smallest prime factor is 7, and 91 = 7 × 13. That is not 91 itself, so 91 is not prime. The nearest primes are 89 below and 97 above, with nothing in between.

91 is an easy number to mistake for a prime. It is not even, and it survives 3 and 5, so anyone who gives up early will call it prime. Only the test against 7 gives it away.

Points to watch

1 is not a prime. The definition starts at 2. If 1 were allowed, a number could be factored in endless ways, such as 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3, and factorisation would no longer be unique.

2 is the only even prime, and it is also the smallest prime of all. Enter n = 2 and the previous prime field shows a hyphen, meaning there is no prime below it.

The gaps between primes are irregular. Between 89 and 97 there is a run of 8, while 11 and 13 sit only 2 apart. Primes thin out as numbers grow, but they never run out.