A quick check that a number is prime

This page shows how to do a quick check that a number $n \lt 300$ is prime. It gives some simple arithmetic rules to check divisibility you can do in your head, has a calculator that shows the steps, and some background theory.

The Algorithm
Why does this work?
Definition of divisible
Rules to check that a number is divisible by a small prime
Pseudo Code
A calculator
See also
Contact us
Post a comment

The Algorithm

To check if a number $n \lt300$ is prime do the following

First memorise the first 6 "small" primes $\{2, 3, 5, 7, 11, 13\}$. If your number is one of these, then it is prime and we are done.
If $n$ is divisible by any of these it is not prime. So stop.
You only need to check the small primes less than the square root of $n$. If none of those divide $n$, then the number is prime. Here is a table showing the checks you need to make:

If n is Check for divisors

<5²= 25 2, 3

<7²= 49 2, 3, 5

<11²= 121 2, 3, 5, 7

<13²= 169 2, 3, 5, 7, 11

<17²= 289 2, 3, 5, 7, 11, 13

If n is	Check for divisors
<5²= 25	2, 3
<7²= 49	2, 3, 5
<11²= 121	2, 3, 5, 7
<13²= 169	2, 3, 5, 7, 11
<17²= 289	2, 3, 5, 7, 11, 13

So, for example, $n=19$ is less than $5^2=25$ so we only have to check for divisibility by primes less than 5, namely 2 and 3.

Is 19 divisible by 2? No, because it is not even; so continue...
Is 19 divisible by 3? No. The sum of the digits is $1 + 9=10$ which is not divisible by 3; so continue...
Ah, but 19 is less than $5^2=25$ so no need to check using 5. So stop. Therefore 19 is a prime.

Similarly $n=43$ is less than $7^2=49$ so we only have to check using $\{2,3,5\}$;

Is 43 divisible by 2? No, so continue...
Is 43 divisible by 3? $4+3=7$, not divisible by 3, so continue...
Is 43 divisible by 5? No, it does not end in 5 or 0, so continue...
But 43 is less than $7^2=49$ so no need to check using 7. So stop. 43 is a prime.

And $n=163$ is less than $13^2=169$, so we only have to check using $\{2,3,5,7,11\}$.

Is 163 divisible by 2? No, so continue...
Is 163 divisible by 3? $1+6+3=10$, not divisible by 3, so continue...
Is 163 divisible by 5? No, it does not end in 5 or 0, so continue...
Is 163 divisible by 7? By the rule, $16 -2\times3=10$, so not divisible by 7, so continue...
Is 163 divisible by 11? By the rule, $1+3 =4 \ne 6$, so not divisible by 11, so continue...
But 163 is less than $13^2=169$ so no need to check using 13. So stop. 1633 is a prime.

Why does this work?

First recall the definition of a prime number

A prime number is defined as an integer, greater than one, that is only divisible by the number one and itself.

An integer $n \gt 1$ which is not prime is called composite and is divisible by a number less than $n$. The number one is neither prime nor composite. If a number is composite THEN it is NOT prime. This is the test we shall use.

Then we use the following theorem

If a number $n$ is composite, it is divisible by a prime number not greater than its square root.

When we say the square root of $n$, we mean the integer square root (strictly denoted $\lfloor\sqrt{n}\rfloor$) - the real square root of the number rounded down to the nearest whole number. So the integer square root of $200$ is $14$ since $\sqrt{200} = 14.142$ which is rounded down to $14$.

Note you don't need to work out the square root, if the prime number you want to check is $p$ and the number $n \lt p^2$ then you can stop checking.

Definition of divisible

We say that the integer $n$ is divisible by an integer $d$ if and only if there exists an integer $a$ such that $n = ad$, or, alternatively, that the remainder on dividing $n$ by $d$ is zero.

So, for example, 4 is divisible by 2 and 18 is divisible by 3, but 7 is not divisible by 2 and 12 is not divisible by 5.

See Rules to check that a number is divisible by a small prime.

Rules to check that a number is divisible by a small prime

Divisible by 2

If a number is even it is divisible by 2: so if the number ends in $\{2, 4, 6, 8, 0\}$ it is not prime (except for 2 itself)

Divisible by 3

A number is divisible by 3 if the sum of its digits is divisible by 3.

So $87$ is divisible by three because $8+7=15$ is divisible by three. And $123$ is divisible by three because $1+2+3= 6$ is divisible by three. But $199$ is not divisible by three because $1 + 1 + 9 = 11$ is not divisible by three.

Divisible by 5

Any number ending in 5 or 0 is divisible by 5.

Divisible by 7

A number is divisible by 7 if the number formed by removing the last digit and subtracting two times that digit from the remaining number is also divisible by 7 (or is zero).

So 91 is divisible by 7 because $9 - 2 \times 1 = 7$ is divisible by 7
119 is divisible by 7 because $11 - 2 \times 9 = -7$ is divisible by 7
42 is divisible by 7 because $4 - 2 \times 2 = 0$ is divisible by 7
But 73 is not divisible by 7 because $7 - 2 \times 3 = 1$ is not divisible by 7

Alternatively if you are above a certain age and can remember long division, then you could check $73$ by noting that 7 into 7 goes once with remainder 0 and 7 does not divide 3 so $73$ is not divisible by 7. And to check $91$ note that 7 into 9 goes once with remainder 2 and 7 divides 21 exactly, so $91$ is divisible by 7.

Divisible by 11

A 3-digit number is divisible by 11 if the sum of the outer digits equals the inner digit.

So $110$ has $1 + 0 = 1$, and $121$ has $1 + 1 = 2$, and $198$ has $1 + 8 = 9$. All these are divisible by 11.

If the sum of the outer digits is greater than 10, then take the remainder after dividing by 11 (or keep subtracting 11 until it's less than 10).

The number $209$ is divisible by 11 since $2+9 = 11 \equiv 0 \pmod{11}$ is equal to the middle digit $0$.

For numbers less than 100 it should be obvious that $22, 33, 44, \ldots, 88, 99$ are divisible by 11 (but note that all of these numbers are already divisible by a lesser prime, so will be caught at an earlier stage if we're checking for primes).

Divisible by 13

A number is divisible by 13 if the number formed by removing the last digit and adding four times that digit to the remaining number is also divisible by 13 (or is zero).

So $52$ is divisible by 13 since $5 + 4 \times 2=13$ is divisible by 13. And $169$ is divisible by 13 since $16 + 4 \times 9 = 52$ is divisible by 13 (you can keep doing this check recursively until the result is obvious).

Pseudo Code

    \begin{algorithm}
    \caption{Test if $n \lt 300$ is prime}
    \begin{algorithmic}
	\INPUT An integer $n$ in the range $1 \lt n \lt 300$
	\OUTPUT \TRUE if $n$ is prime; else \FALSE.
		\IF{$n \in \{2,3,5,7,11,13\}$}
			\STATE \RETURN \TRUE
		\ENDIF
		\FOR{$p$ in $(2,3,5,7,11,13)$}
			\IF{$p\mid n$}
				\STATE \RETURN \FALSE
			\ENDIF
			\IF{$n \lt p^2$}
				\STATE \RETURN \TRUE
			\ENDIF
		\ENDFOR
		\COMMENT{\sffamily Deal with $17^2 \le n \lt 300 $}
        \IF{$n = 289$} 
            \STATE \RETURN \FALSE
		\ELSE
            \STATE \RETURN \TRUE
        \ENDIF
    \end{algorithmic}
    \end{algorithm}

Many thanks to Saswat Padhi and colleagues for the pseudocode.js JavaScript library that typesets pseudocode beautifully to HTML.

Extending this test to $ 289 \le n\lt 300$

The astute reader will notice that the basic algorithm only works up to $17^2 = 289$. To extend it to the nice round number 300 we note that

If $n=17^2=289$ then it is divisible by 17 and therefore not prime.
Otherwise, if $n$ has passed all the prior divisibility tests for $2\ldots 13$ and is less than 300, then it must be prime (the only prime number in that range is 293).
If $n \gt 300$ then we stop and return "undefined" or some other out-of-range error.

A calculator

This calculator demonstrates the above algorithm. It will accept a number, state whether or not it's prime, and show the steps described above.